Model-theoretic complexity of automatic structures
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 autom...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Elsevier
2015
|
| Online Access: | http://hdl.handle.net/1721.1/96326 |
| _version_ | 1826216159954862080 |
|---|---|
| author | Khoussainov, Bakhadyr Minnes, Mia |
| author2 | Massachusetts Institute of Technology. Department of Mathematics |
| author_facet | Massachusetts Institute of Technology. Department of Mathematics Khoussainov, Bakhadyr Minnes, Mia |
| author_sort | Khoussainov, Bakhadyr |
| collection | MIT |
| 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 ω[superscript ω]. (2) The ordinal heights of automatic well-founded relations are unbounded below ω[subscript 1 superscript CK], the first non-computable ordinal. (3) For any computable ordinal α, there is an automatic structure of Scott rank at least αα. Moreover, there are automatic structures of Scott rank ω[subscript 1 superscript CK],ω[subscript 1 superscript CK] +1. (4) For any computable ordinal α, there is an automatic successor tree of Cantor–Bendixson rank α. |
| first_indexed | 2024-09-23T16:42:54Z |
| format | Article |
| id | mit-1721.1/96326 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T16:42:54Z |
| publishDate | 2015 |
| publisher | Elsevier |
| record_format | dspace |
| spelling | mit-1721.1/963262022-09-29T21:00:20Z Model-theoretic complexity of automatic structures Khoussainov, Bakhadyr Minnes, Mia Massachusetts Institute of Technology. Department of Mathematics Minnes, Mia 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 ω[superscript ω]. (2) The ordinal heights of automatic well-founded relations are unbounded below ω[subscript 1 superscript CK], the first non-computable ordinal. (3) For any computable ordinal α, there is an automatic structure of Scott rank at least αα. Moreover, there are automatic structures of Scott rank ω[subscript 1 superscript CK],ω[subscript 1 superscript CK] +1. (4) For any computable ordinal α, there is an automatic successor tree of Cantor–Bendixson rank α. Marsden Fund 2015-04-02T16:00:24Z 2015-04-02T16:00:24Z 2009-08 Article http://purl.org/eprint/type/JournalArticle 01680072 http://hdl.handle.net/1721.1/96326 Khoussainov, Bakhadyr, and Mia Minnes. “Model-Theoretic Complexity of Automatic Structures.” Annals of Pure and Applied Logic 161, no. 3 (December 2009): 416–426. © 2009 Elsevier B.V. en_US http://dx.doi.org/10.1016/j.apal.2009.07.012 Annals of Pure and Applied Logic Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Elsevier Elsevier |
| spellingShingle | Khoussainov, Bakhadyr Minnes, Mia Model-theoretic complexity of automatic structures |
| title | Model-theoretic complexity of automatic structures |
| title_full | Model-theoretic complexity of automatic structures |
| title_fullStr | Model-theoretic complexity of automatic structures |
| title_full_unstemmed | Model-theoretic complexity of automatic structures |
| title_short | Model-theoretic complexity of automatic structures |
| title_sort | model theoretic complexity of automatic structures |
| url | http://hdl.handle.net/1721.1/96326 |
| work_keys_str_mv | AT khoussainovbakhadyr modeltheoreticcomplexityofautomaticstructures AT minnesmia modeltheoreticcomplexityofautomaticstructures |