Bakhadyr Khoussainov ; Andre Nies ; Sasha Rubin ; Frank Stephan - Automatic Structures: Richness and Limitations

lmcs:2219 - Logical Methods in Computer Science, April 26, 2007, Volume 3, Issue 2 -
Automatic Structures: Richness and Limitations

Authors: Bakhadyr Khoussainov ; Andre Nies ORCID-iD; Sasha Rubin ORCID-iD; Frank Stephan ORCID-iD

    We study the existence of automatic presentations for various algebraic structures. An automatic presentation of a structure is a description of the universe of the structure by a regular set of words, and the interpretation of the relations by synchronised automata. Our first topic concerns characterising classes of automatic structures. We supply a characterisation of the automatic Boolean algebras, and it is proven that the free Abelian group of infinite rank, as well as certain Fraisse limits, do not have automatic presentations. In particular, the countably infinite random graph and the random partial order do not have automatic presentations. Furthermore, no infinite integral domain is automatic. Our second topic is the isomorphism problem. We prove that the complexity of the isomorphism problem for the class of all automatic structures is \Sigma_1^1-complete.

    Volume: Volume 3, Issue 2
    Published on: April 26, 2007
    Submitted on: September 15, 2006
    Keywords: Computer Science - Discrete Mathematics,Computer Science - Logic in Computer Science,F.1.1,F.4.3

    Linked data

    Source : ScholeXplorer IsReferencedBy DOI 10.1007/978-3-319-50062-1_24
    • 10.1007/978-3-319-50062-1_24
    • 10.1007/978-3-319-50062-1_24
    Injection Structures Specified by Finite State Transducers
    Buss, Sam ; Cenzer, Douglas ; Minnes, Mia ; Remmel, Jeffrey B. ;

    28 Documents citing this article


    Consultation statistics

    This page has been seen 430 times.
    This article's PDF has been downloaded 260 times.