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

Authors: Bakhadyr Khoussainov André Nies Sasha Rubin Frank Stephan

Abstract

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.

BibTeX

  @InProceedings{KhoussainovNiesRubi-AutomaticStructures,
    author = 	 {Bakhadyr Khoussainov and André Nies and Sasha Rubin and Frank Stephan},
    title = 	 {Automatic Structures: Richness and Limitations},
    booktitle =  {Proceedings of the Nineteenth Annual IEEE Symposium on Logic in Computer Science (LICS 2004)},
    year =	 {2004},
    month =	 {July}, 
    pages =      {44--53},
    location =   {Turku, Finland}, 
    publisher =	 {IEEE Computer Society Press}
  }