Abstract:
The work at hand studies properties of structures that have certain types of algorithmic description. In particular, we study the fundamental properties of three classes of structures. The first class is the class of finite structures, which can be algorithmically described by listing all elements and tuples of atomic relations. The second class is the class of automatic structures, which are possibly infinite structures whose descriptions consist of automata representing their universe and relations. These structures attract attention as their firstorder theories are decidable. The third class is the class of computable structures, which are structures given by Turing machines. For finite structures, we address the efficiency of deciding the winners in Ehrenfeucht- Fräıss'e games (EF games for short) for some standard classes of structures. EF game is an important tool in finite model theory in demonstrating the expressive power of firstorder logic and its extensions. We present algorithms that decide which player wins EF games played on structures that are taken fromthe following classes: structureswith unary predicates, equivalence structures and some of their expansions, treeswith level predicates and Boolean algebras with distinguished ideals. Under some natural assumptions on the representations of these structures and EF games, we will prove all algorithms run in constant time. We then investigate a special subclass of automatic structures, the class of unary automatic structures. These structures are described using automata over a unary alphabet. We present uniform and efficient algorithms to decide certain graph-theoretical properties for the class of unary automatic graphs with finite degree. We also provide efficient algorithms for deciding the isomorphismproblemfor unary automatic linear orders, equivalence structures and trees. We also extend the notion of state complexity from regular languages to structures and study this in the context of unary automatic structures. For automatic structures in general, the isomorphism problem is highly undecidable ([Sigma]11-complete). We show that undecidability also holds for some natural subclasses of automatic structures. In particular, we show that the isomorphism problem for automatic equivalence structures is [Pi]01-complete; the isomorphism problem for automatic successor trees of finite height k [greater than or equal to] 2 is [Pi]02(k-3)-complete; the isomorphism problem for automatic linear orders is hard for every level of the arithmetic hierarchy. We also illustrate that for any k [element of] IN, there exist two isomorphic automatic trees of finite height (and two automatic linear orders) without any [Sigma]0k-isomorphism. These solve some known open questions in the area, in particular, questions posed by Khoussainov and Nerode. Lastly, we study computable categoricity of computable structures. A computable structure is computably categorical if any two computable presentation of it are computably isomorphic. We focus on the class of computably categorical graphs. In particular, we investigate the strongly locally finite graphs: graphs all of whose components are finite. We present a necessary and sufficient condition for certain classes of strongly locally finite graphs to be computably categorical. We show that whenever the graph contains an infinite [Delta]02-set of components that can be properly embedded into infinitely many components of the graph, then the graph is not computably categorical. We also construct a strongly locally finite computably categorical graph with an infinite chain of properly embedded components.