Khoussainov and Nerode [14] posed various open questions on model-theoretic properties of automatic structures. In this work we answer some of these questions by showing the following results: There is an uncountably categorical but not countably categorical theory for which only the prime model is automatic; There are complete theories with exactly 3,4,5,…3,4,5,… countable models, respectively, and every countable model is automatic; There is a complete theory for which exactly 2 models have an automatic presentation; If LOGSPACE=PLOGSPACE=P then there is (...) an uncountably categorical but not countably categorical theory for which the prime model does not have an automatic presentation but all the other countable models are automatic; There is a complete theory with countably many countable models for which the saturated model has an automatic presentation but the prime model does not have one. (shrink)

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 ( $\Sigma _{1}^{1}\text{-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 $\Sigma _{1}^{1}\text{-complete}$ , resp.). (shrink)

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 strengthens a recent result by Hjorth, Khoussainov, Montalbán, and Nies showing that the isomorphism problem for ω-automatic structures is not in . Moreover, assuming the continuum hypothesis CH, we can show that the isomorphism problem for ω-automatic trees of finite height is recursively equivalent with second-order arithmetic. On the way to (...) our main results, we show lower and upper bounds for the isomorphism problem for ω-automatic trees of every finite height: It is decidable , for height 1 , -hard and in for height 3, and - and -hard and in for height . All proofs are elementary and do not rely on theorems from set theory. (shrink)

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 that the first-order theory of a string automatic structure of bounded degree is decidable in doubly exponential space (for injective automatic presentations, this holds even uniformly). This result is shown to be optimal since we also present a string automatic structure of bounded degree whose first-order theory is hard for 2EXPSPACE. We prove similar (...) results also for tree automatic structures. These findings close the gaps left open in [28] by improving both the lower and the upper bounds. (shrink)

We consider ω n -automatic structures which are relational structures whose domain and relations are accepted by automata reading ordinal words of length ω n for some integer n ≥ 1. We show that all these structures are ω-tree-automatic structures presentable by Muller or Rabin tree automata. We prove that the isomorphism relation for ω 2 -automatic (resp. ω n -automatic for n > 2) boolean algebras (respectively, partial orders, rings, commutative rings, non commutative rings, non commutative groups) is not (...) determined by the axiomatic system ZFC. We infer from the proof of the above result that the isomorphism problem for ω n -automatic boolean algebras, n ≥ 2, (respectively, rings, commutative rings, non commutative rings, non commutative groups) is neither a ${\mathrm{\Sigma }}_{2}^{1}-\mathrm{s}\mathrm{e}\mathrm{t}$ nor a ${\mathrm{\Pi }}_{2}^{1}-\mathrm{s}\mathrm{e}\mathrm{t}$ . We obtain that there exist infinitely many ω n -automatic, hence also ω-tree-automatic, atomless boolean algebras $\mathcal{B}_{n}$ , n ≥ 1, which are pairwise isomorphic under the continuum hypothesis CH and pairwise non isomorphic under an alternate axiom AT, strengthening a result of [14]. (shrink)