Automatic Structures: Richness and Limitations

Details Automatic Structures: Richness and Limitations Automatic Structures: Richness and Limitations

2007-03-13

arxiv.org/abs/cs/0703064v2

LMCS 3 (2:2) 2007

Computer Science

Discrete Mathematics

Scientific paper

10.2168/LMCS-3(2:2)2007

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.

Affiliated with

Also associated with

No associations

Rating

Automatic Structures: Richness and Limitations does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Automatic Structures: Richness and Limitations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Automatic Structures: Richness and Limitations will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-438789