Nineteenth Annual IEEE Symposium on

Logic in Computer Science (LICS 2004)

Paper: Automatic Structures: Richness and Limitations (at LICS 2004)

Authors: Bakhadyr Khoussainov Andre Nies Sasha Rubin Frank Stephan


This paper studies the existence of automatic presentations for various algebraic structures. The automatic Boolean algebras are characterised, and it is proven that the free Abelian group of infinite rank and many Fraïssé limits do not have automatic presentations. In particular, the countably infinite random graph and the universal partial order do not have automatic presentations. Furthermore, no infinite integral domain is automatic. The second topic of the paper is the isomorphism problem. We prove that the complexity of the isomorphism problem for the class of all automatic structures is \sum\nolimits_1^1-complete.


    author = 	 {Bakhadyr Khoussainov and Andre Nies and Sasha Rubin and Frank Stephan},
    title = 	 {Automatic Structures: Richness and Limitations},
    booktitle =  {Proceedings of the Nineteenth Annual IEEE Symp. on Logic in Computer Science, {LICS} 2004},
    year =	 2004,
    editor =	 {Harald Ganzinger},
    month =	 {July}, 
    pages =      {44--53},
    location =   {Turku, Finland}, 
    publisher =	 {IEEE Computer Society Press}