some image logo

HOME

SEARCH

CURRENT ISSUE

REGULAR ISSUES

   Volume 1 (2005)

   Volume 2 (2006)

   Volume 3 (2007)

      Issue 1

      Issue 2

      Issue 3

      Issue 4

   Volume 4 (2008)

   Volume 5 (2009)

   Volume 6 (2010)

   Volume 7 (2011)

   Volume 8 (2012)

   Volume 9 (2013)

   Volume 10 (2014)

SPECIAL ISSUES

SURVEY ARTICLES

AUTHORS

ABOUT

SERVICE

LOGIN

FAQ

SUPPORT

CONTACT

VOLUME 3, ISSUE 2, PAPER 2


Automatic Structures: Richness and Limitations

©Bakhadyr Khoussainov, University of Auckland
©Andre Nies, University of Auckland
©Sasha Rubin, University of Auckland
©Frank Stephan, National University of Singapore

Abstract
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 Σ_1^1-complete.

Publication date: April 26, 2007

Full Text: PDF | PostScript
DOI: 10.2168/LMCS-3(2:2)2007

Hit Counts: 5769

Creative Commons