Model Theoretic Complexity of Automatic Structures

Details Model Theoretic Complexity of Automatic Structures Model Theoretic Complexity of Automatic Structures

2008-09-19

arxiv.org/abs/0809.3425v1

Mathematics

Logic

23 pages. Extended abstract appeared in Proceedings of TAMC '08, LNCS 4978 pp 514-525

Scientific paper

We study the complexity of automatic structures via well-established concepts from both logic and model theory, including ordinal heights (of well-founded relations), Scott ranks of structures, and Cantor-Bendixson ranks (of trees). We prove the following results: 1) The ordinal height of any automatic well- founded partial order is bounded by \omega^\omega ; 2) The ordinal heights of automatic well-founded relations are unbounded below the first non-computable ordinal; 3) For any computable ordinal there is an automatic structure of Scott rank at least that ordinal. Moreover, there are automatic structures of Scott rank the first non-computable ordinal and its successor; 4) For any computable ordinal, there is an automatic successor tree of Cantor-Bendixson rank that ordinal.

Affiliated with

Also associated with

No associations

Rating

Model Theoretic Complexity of Automatic Structures 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 Model Theoretic Complexity of Automatic Structures, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Model Theoretic Complexity of Automatic Structures will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-158016