Model Theoretic Complexity of Automatic Structures
| dc.creator | Khoussainov, Bakhadyr | |
| dc.creator | Minnes, Mia | |
| dc.date | 2008-09-19 | |
| dc.date.accessioned | 2026-07-07T10:04:05Z | |
| dc.date.available | 2026-07-07T10:04:05Z | |
| dc.description | 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 ω^ω; 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. | |
| dc.description | 23 pages. Extended abstract appeared in Proceedings of TAMC '08, LNCS 4978 pp 514-525 | |
| dc.identifier | https://arxiv.org/abs/0809.3425 | |
| dc.identifier | http://arxiv.org/abs/0809.3425 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/169536 | |
| dc.subject | Logic | |
| dc.subject | 03D05, 68Q70, 68Q45 | |
| dc.title | Model Theoretic Complexity of Automatic Structures | |
| dc.type | text |