Automatic structures made their appearance at LICS twenty years ago, at LICS 2000.
However, their roots are much older. The idea of automata based decision procedures for …

In this paper we introduce the concept of a Cayley graph automatic group (CGA group or
graph automatic group, for short) which generalizes the standard notion of an automatic …

The objective of this survey is to present the ideal theory of monoids, the so-called Green's
relations, and to illustrate the usefulness of this tool for solving automata related questions …

We study the relative complexity of equivalence relations and preorders from computability
theory and complexity theory. Given binary relations R, S, a componentwise reducibility is …

We study structures that are automatic with advice. These are structures that admit a
presentation by finite automata (over finite or infinite words or trees) with access to an …

Regular languages are languages recognised by finite automata; automatic structures are a
generalisation of regular languages where one also uses automatic relations (which are …

The computational complexity of the isomorphism problem for regular trees, regular linear
orders, and regular words is analyzed. A tree is regular if it is isomorphic to the prefix order …

The two central topics of this book are (i) the model checking problem for specific structures
and (ii) the study of the expressive power of various logics. To this end we will develop …

Automata Theory is the science of the treatment of languages (sets of words over a finite
alphabet) from an algorithmic and theoretical viewpoint; there are also connections to the …

The main result of this paper states that the isomorphism problem for ω-automatic trees of
finite height is at least has hard as second-order arithmetic and therefore not analytical. This …