Paper: From Automatic Structures to Borel Structures (at LICS 2008)

Authors: Greg Hjorth Bakhadyr Khoussainov Antonio Montalbán André Nies

Abstract

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.

BibTeX

  @InProceedings{MontalbnNies-FromAutomaticStruct,
    author = 	 {Greg Hjorth and Bakhadyr Khoussainov and Antonio Montalbán and André Nies},
    title = 	 {From Automatic Structures to Borel Structures},
    booktitle =  {Proceedings of the Twenty-Third Annual IEEE Symposium on Logic in Computer Science (LICS 2008)},
    year =	 {2008},
    month =	 {June}, 
    pages =      {431--441},
    location =   {Pittsburgh, PA, USA}, 
    publisher =	 {IEEE Computer Society Press}
  }