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 automatic well-founded partial order is bounded by ω ω . (2) The ordinal heights of automatic well-founded relations are unbounded below ω 1 C K , 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 ω 1 C K , ω 1 C K + 1 . (4) For any computable ordinal α , there is an automatic successor tree of Cantor–Bendixson rank α .