From Automatic Structures to Borel Structures

We study the classes of Büchi and Rabin automatic structures. For  Büchi (Rabin) automatic structures their domains consist of  infinite strings (trees), and the basic relations, including the equality relation, and graphs  of operations are recognized by  Büchi (Rabin) automata. A     Büchi (Rabin) automatic structure is injective if different infinite strings (trees) represent different elements of the structure. The first part of the paper is devoted to understanding the automata-theoretic content of the well-known Löwenheim-Skolem theorem in model theory. We provide  automata-theoretic versions of Löwenheim-Skolem theorem for Rabin and Büchi automatic structures. In the second part, we address the following two well-known open problems in the theory of automatic structures: Does every Büchi automatic structure have an injective Büchi presentation? Does every Rabin automatic structure have an injective Rabin presentation?  We provide examples of Büchi structures without injective Büchi and Rabin presentations. To answer these questions we introduce Borel structures and usesome of the basic properties of Borel sets and isomorphisms. Finally, in the last part of the paper we study the isomorphism problem for Büchi automatic structures.