# A hierarchy of tree-automatic structures

@article{Finkel2012AHO, title={A hierarchy of tree-automatic structures}, author={Olivier Finkel and Stevo Todorcevic}, journal={The Journal of Symbolic Logic}, year={2012}, volume={77}, pages={350 - 368} }

Abstract We consider ωn-automatic structures which are relational structures whose domain and relations are accepted by automata reading ordinal words of length ωn for some integer n ≥ 1. We show that all these structures are ω-tree-automatic structures presentable by Muller or Rabin tree automata. We prove that the isomorphism relation for ω2-automatic (resp. ωn-automatic for n > 2) boolean algebras (respectively, partial orders, rings, commutative rings, non commutative rings, non commutative…

#### Topics from this paper

#### 8 Citations

Pumping for ordinal-automatic structures

- Mathematics, Computer ScienceComput.
- 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.

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

- Computer Science, MathematicsJ. 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.

The isomorphism problem for tree-automatic ordinals with addition

- Mathematics, Computer ScienceInf. Process. Lett.
- 2019

An algorithm is described that, given two tree-automatic ordinals with the ordinal addition operation, decides if the ordinals are isomorphic.

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,…

Automatic Ordinals

- Computer Science, MathematicsInt. J. Unconv. Comput.
- 2013

It is proved that the injectively ω-tree-automatic ordinals are the ordinals smaller than ω ω and that the hierarchy of injectivelyω-automatic structures, n ≥ 1, which was considered in [FT12], is strict.

Tree-automatic scattered linear orders

- Computer Science, MathematicsTheor. Comput. Sci.
- 2016

It is shown that there is no tree-automatic scattered linear order, and therefore no tree's automatic well-order, on the set of all finite labeled trees, and that a regular tree language admits a tree- automatic scattered linear orders if and only if for some n, no binary tree of height n can be embedded into the union of the domains of its trees.

Deciding parity games in quasipolynomial time

- Computer Science, MathematicsSTOC
- 2017

It is shown that the parity game can be solved in quasipolynomial time and it is proven that coloured Muller games with n nodes and m colours can be decided in time O((mm · n)5); it is also shown that this bound cannot be improved to O((2m · n), for any c, unless FPT = W[1].

Deciding Parity Games in Quasi-polynomial Time

- Mathematics
- 2020

It is shown that the parity game can be solved in quasi-polynomial time. The parameterized parity game---with $n$ nodes and $m$ distinct values (a.k.a. colors or priorities)---is proven to be in th...

#### References

SHOWING 1-10 OF 64 REFERENCES

The isomorphism relation between tree-automatic Structures

- Mathematics, Computer ScienceArXiv
- 2010

It is proved that the isomorphism relation for ω-tree-automatic boolean algebras is not determined by the axiomatic system ZFC and is neither a Σ21- set nor a Π21-set.

Finite Presentations of Infinite Structures:
Automata and Interpretations

- Mathematics, Computer ScienceTheory 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.

Automatic structures

- Computer ScienceProceedings 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.

The Isomorphism Problem for omega-Automatic Trees

- Mathematics, Computer ScienceCSL
- 2010

The main result of this paper is that the isomorphism for omega-automatic trees of finite height is at least has hard as second-order arithmetic and therefore not analytical. This strengthens a…

From Automatic Structures to Borel Structures

- Mathematics, Computer Science2008 23rd Annual IEEE Symposium on Logic in Computer Science
- 2008

Borel structures are introduced and some of the basic properties of Borel sets and isomorphisms are used to answer the isomorphism problem for Buchi automatic structures.

First-order and counting theories of ω-automatic structures

- MathematicsJournal of Symbolic Logic
- 2008

Abstract The logic extends first-order logic by a generalized form of counting quantifiers (“the number of elements satisfying … belongs to the set C”). This logic is investigated for structures with…

First-order and counting theories of omega-automatic structures

- Mathematics, Computer ScienceJ. Symb. Log.
- 2008

It is shown that, as in the case of automatic structures, also modulo-counting quantifiers as well as infinite cardinality quantifiers lead to decidable theories.

An Eilenberg Theorem for Words on Countable Ordinals

- Mathematics, Computer ScienceLATIN
- 1998

It is shown that finite Ω1-semigroups are equivalent to automata, and the proof gives a new algorithm for determinizing automata on countable ordinals.

Computer science and the fine structure of Borel sets

- Computer Science, MathematicsTheor. Comput. Sci.
- 2001

This work gives a transparent restatement and proof of Wadge's main theorem, and extends Wagner's results to more general kinds of automata: counters, push-down automata and Buchi automata reading transfinite words.

Decidability of second-order theories and automata on infinite trees

- Mathematics
- 1968

Introduction. In this paper we solve the decision problem of a certain secondorder mathematical theory and apply it to obtain a large number of decidability results. The method of solution involves…