# The Field of the Reals and the Random Graph are not Finite-Word Ordinal-Automatic

@article{Kartzow2016TheFO, title={The Field of the Reals and the Random Graph are not Finite-Word Ordinal-Automatic}, author={Alexander Kartzow}, journal={ArXiv}, year={2016}, volume={abs/1410.5197} }

Recently, Schlicht and Stephan lifted the notion of automatic-structures to the notion of (finite-word) ordinal-automatic structures. These are structures whose domain and relations can be represented by automata reading finite words whose shape is some fixed ordinal $\alpha$. We lift Delhomm\'e's relative-growth-technique from the automatic and tree-automatic setting to the ordinal-automatic setting. This result implies that the random graph is not ordinal-automatic and infinite integral… Expand

#### Topics from this paper

#### 2 Citations

Algorithmic Solutions via Model Theoretic Interpretations

- Mathematics
- 2017

Model theoretic interpretations are an important tool in algorithmic model theory. Their applications range from reductions between logical theories to the construction of algorithms for problems,… Expand

Technical Report Column

- Computer Science
- SIGA
- 2014

Simultaneous Approximation of Constraint Satisfaction Problems, Amey Bhangale, Swastik Kopparty, Sushant Sachdeva, TR14-098. The Complexity of DNF of Parities, Gil Cohen, Igor Shinkar, TR14-099. The… Expand

#### References

SHOWING 1-10 OF 19 REFERENCES

Structures without Scattered-Automatic Presentation

- Mathematics, Computer Science
- CiE
- 2013

This paper proves the following limitations on the class of \(\mathfrak{L}\)-automatic structures for a fixed \(\ mathfrak {L}\) of finite condensation rank 1 + α. Expand

The Rank of Tree-Automatic Linear Orderings

- Mathematics, Computer Science
- STACS
- 2013

It is proved that the FC-rank of every tree-automatic linear ordering is below omega^omega, and an analogue for tree- automatic linear orderings where the branching complexity of the trees involved is bounded is shown. Expand

A hierarchy of tree-automatic structures

- Mathematics, Computer Science
- The Journal of Symbolic Logic
- 2012

It is obtained that there exist infinitely many ωn- automatic, hence also ω-tree-automatic, atomless boolean algebras, which are pairwise isomorphic under the continuum hypothesis CH and pairwise non isomorph under an alternate axiom AT, strengthening a result of [14]. Expand

Pumping for ordinal-automatic structures

- Mathematics, Computer Science
- Comput.
- 2017

A pumping lemma for alpha-automata (processing finite alpha-words, i.e., words of length alpha that have one fixed letter at all but finitely many positions) is developed and a sharp bound on the height of the finite word alpha-automatic well-founded order forests is provided. Expand

Model-theoretic complexity of automatic structures

- Mathematics, Computer Science
- Ann. Pure Appl. Log.
- 2009

The following results are proved: The ordinal height of any automatic well-founded partial order is bounded by ωω, and the ordinal heights of automaticWell-founded relations are unbounded below (ω1CK). Expand

Automatic linear orders and trees

- Mathematics, Computer Science
- TOCL
- 2005

It is shown that every infinite path in an automatic tree with countably many infinite paths is a regular language. Expand

Automata on ordinals and automaticity of linear orders

- Mathematics, Computer Science
- Ann. Pure Appl. Log.
- 2013

A method for proving non-automaticity is described and this is applied to determine the optimal bounds for the ranks of linear orders recognized by finite state automata. Expand

Tree-Automatic Well-Founded Trees

- Mathematics, Computer Science
- CiE
- 2012

It is shown that the isomorphism problem for tree-automatic well-founded trees is complete for level $\Delta^0_{\omega^ \omega}$ of the hyperarithmetical hierarchy (under Turing-reductions). Expand

Transfinite Automata Recursions and Weak Second Order Theory of Ordinals

- Mathematics
- 1990

We identify the ordinal α with the set of all ordinals x < α. The weak second order theory of [α, <] is the interpreted formalism WST [α, <] which makes use of: (a) the propositional connectives with… Expand

Automatic structures: richness and limitations

- Computer Science, Mathematics
- Proceedings of the 19th Annual IEEE Symposium on Logic in Computer Science, 2004.
- 2004

It is proven that the free Abelian group of infinite rank and many Fraisse limits do not have automatic presentations, and the complexity of the isomorphism problem for the class of all automatic structures is /spl Sigma//sub 1//sup 1/-complete. Expand