The Journal of Symbolic Logic

Research Article

Some natural decision problems in automatic graphs

Dietrich Kuskea1 and Markus Lohreya2

a1 Labri, CNRS, Université Bordeaux I, 351, Cours de la Libération F-33405 Talence, France. E-mail:

a2 Universität Leipzig, Institut für Informatik Postfach 100920, D-04009 Leipzig, Germany. E-mail:


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, bounding the number of ends, and bounding the number of infinite branches in a tree

(C) existence of an infinite clique and an infinite version of set cover

The complexity of these problems is determined for automatic graphs and. supplementing results from the literature, for recursive graphs. Our results show that these problems

(A) are equally complex for automatic and for recursive graphs (-complete).

(B) are moderately less complex for automatic than for recursive graphs (complete for different levels of the arithmetic hierarchy),

(C) are much simpler for automatic than for recursive graphs (decidable and -complete, resp.).

(Received October 30 2008)