We study definability problems and algorithmic issues for infinite structures that are finitely
presented. After a brief overview over different classes of finitely presentable structures, we …

In addition to the most common logical systems such as first-order and second-order logic
(and their fragments), this survey focuses on algorithmic questions and complexity results …

Preface. This paper grew out of three tutorial lectures on automatic structures given at the
LogicColloquium2007 inWrocław (Poland). The paper will follow the outline of the tutorial …

Résumé Les structures automatiques (resp. arbre-automatiques) sont les structures
relationnelles dont le domaine est un ensemble régulier de mots (resp. de termes) finis et …

A structure is said to be computable if its domain can be represented by a set which is
accepted by a Turing machine and if its relations can then be checked using Turing …

The work at hand studies the possibilities and limitations of the use of finite automata in the
description of infinite structures. An automatic presentation of a countable structure consists …

The first-order theory of a string automatic structure is known to be decidable, but there are
examples of string automatic structures with nonelementary first-order theories. We prove …

The logic extends first-order logic by a generalized form of counting quantifiers (“the number
of elements satisfying… belongs to the set C”). This logic is investigated for structures with …

For automatic and recursive graphs, we investigate the following problems:(A) existence of a
Hamiltonian path and existence of an infinite path in a tree (B) existence of an Euler path …

An algebraic tree T is one determined by a finite system of fixed point equations. The frontier
Fr (T) of an algebraic tree T is linearly ordered by the lexicographic order< ℓ If (Fr (T)< ℓ) is …