文章基本信息

标题：The Rank of Tree-Automatic Linear Orderings
本地全文：下载
作者：Martin Huschenbett
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2013
卷号：20
页码：586-597
DOI：10.4230/LIPIcs.STACS.2013.586
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：tree-automatic structures; linear orderings; finite condensation rank; computable model theory