# Tree-Automatic Well-Founded Trees

@inproceedings{Kartzow2012TreeAutomaticWT, title={Tree-Automatic Well-Founded Trees}, author={Alexander Kartzow and J. Liu and Markus Lohrey}, booktitle={CiE}, year={2012} }

We investigate tree-automatic well-founded trees. For this, we introduce a new ordinal measure for well-founded trees, called ∞-rank. The ∞-rankof a well-founded tree is always bounded from above by the ordinary (ordinal) rank of a tree. We also show that the ordinal rank of a well-founded tree of ∞-rankα is smaller than ω·(α+1). For string-automatic well-founded trees, it follows from [16] that the ∞-rankis always finite. Here, using Delhomme's decomposition technique for tree-automatic… Expand

#### Topics from this paper

#### 6 Citations

Tree-Automatic Well-Founded Trees

- Mathematics, Computer Science
- Log. Methods Comput. Sci.
- 2013

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 with respect to Turing-reductions. Expand

The isomorphism problem on classes of automatic structures with transitive relations

- Mathematics
- 2013

Automatic structures are finitely presented structures where the universe and all relations can be recognized by finite automata. It is known that the isomorphism problem for automatic structures is… Expand

The model-theoretic complexity of automatic linear orders

- Computer Science
- 2015

This thesis studies the model-theoretic complexity of automatic linear orders in terms of two complexity measures: the finite-condensation rank and the Ramsey degree. 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

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

- Computer Science, Mathematics
- J. Autom. Lang. Comb.
- 2016

This work lifts Delhomm\'e's relative-growth-technique from the automatic and tree-automatic setting to the ordinal- automatic setting, which implies that the random graph is not Ordinal-automatic and infinite integral domains are not ordinals below $\omega_1+\omega^ \omega$ where $\omegas_1$ is the first uncountable ordinal. 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

#### References

SHOWING 1-10 OF 24 REFERENCES

Tree-Automatic Well-Founded Trees

- Mathematics, Computer Science
- Log. Methods Comput. Sci.
- 2013

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 with respect to Turing-reductions. 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

The isomorphism problem on classes of automatic structures with transitive relations

- Mathematics
- 2013

Automatic structures are finitely presented structures where the universe and all relations can be recognized by finite automata. It is known that the isomorphism problem for automatic structures is… Expand

Automatic structures

- Computer Science
- Proceedings Fifteenth Annual IEEE Symposium on Logic in Computer Science (Cat. No.99CB36332)
- 2000

This work determines the complexity of model checking and query evaluation on automatic structures for fragments of first-order logic and gives model-theoretic characterisations for automatic structures via interpretations. Expand

Finite Presentations of Infinite Structures:
Automata and Interpretations

- Mathematics, Computer Science
- Theory of Computing Systems
- 2004

The model checking problem for FO(∃ω), first-order logic extended by the quantifier “there are infinitely many”, is proved to be decidable for automatic and ω-automatic structures and appropriate expansions of the real ordered group. Expand

Word Automaticity of Tree Automatic Scattered Linear Orderings Is Decidable

- Computer Science, Mathematics
- CiE
- 2012

It is proved that the problem of whether a given tree automatic structure is already word automatic is decidable for tree automatic scattered linear orderings and in case of a positive answer a word automatic presentation is computable from the tree automatic presentation. Expand

Automatic structures of bounded degree revisited

- Mathematics
- The Journal of Symbolic Logic
- 2011

Abstract The first-order theory of a string automatic structure is known to be decidable, but there are examples of string automatic structures with nonelementary first-order theories. We prove that… Expand

First-Order Model Checking on Generalisations of Pushdown Graphs

- Mathematics, Computer Science
- ArXiv
- 2012

It is proved that first-order logic extended by Ramsey quantifiers is decidable on all tree-automatic structures. Expand

Hausdorff ’s theorem for posets that satisfy the finite antichain property

- Mathematics
- 1999

Hausdorff characterized the class of scattered linear orderings as the least family of linear orderings that includes the ordinals and is closed under ordinal summations and inversions. We formulate… Expand