LIPIcs.STACS.2013.586.pdf
- Filesize: 0.57 MB
- 12 pages
Document
The Rank of Tree-Automatic Linear Orderings
Author
-
Part of:
Volume:
30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Theoretical Aspects of Computer Science (STACS) - License:
Creative Commons Attribution-NoDerivs 3.0 Unported license
- Publication Date: 2013-02-26
Cite AsGet BibTex
Martin Huschenbett. The Rank of Tree-Automatic Linear Orderings. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 586-597, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
https://doi.org/10.4230/LIPIcs.STACS.2013.586
https://doi.org/10.4230/LIPIcs.STACS.2013.586
Abstract
A tree-automatic structure is a structure whose domain can be encoded by a regular tree language such that each relation is recognisable by a finite automaton processing tuples of trees synchronously. The finite condensation rank (FC-rank) of a linear ordering measures how far it is away from being dense. We prove that the FC-rank of every tree-automatic linear ordering is below omega^omega. This generalises Delhommé's result that each tree-automatic ordinal is less than omega^omega^omega. Furthermore, we show an analogue for tree-automatic linear orderings where the branching complexity of the trees involved is bounded.
Keywords
- tree-automatic structures
- linear orderings
- finite condensation rank
- computable model theory
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads