The rank of tree-automatic linear orderings

DOI10.4230/LIPICS.STACS.2013.586MaRDI QIDQ2957918zbMATH OpenOpenAlexFDO

Authors Martin Huschenbett

Publication date 30 January 2017

Full work available at URL https://arxiv.org/abs/1204.3048

zbMATH Keywords

computable model theoryfinite condensation ranklinear orderingstree-automatic structures

Mathematics Subject Classification ID

Computable structure theory, computable model theory (03C57)

Abstract: We generalise Delhomm'e's result that each tree-automatic ordinal is strictly below omega^omega^omega{} by showing that any tree-automatic linear ordering has FC-rank strictly below omega^omega. We further investigate a restricted form of tree-automaticity and prove that every linear ordering which admits a tree-automatic presentation of branching complexity at most k has FC-rank strictly below omega^k.

Recommendations

• Automatic linear orders and trees
• Tree-automatic well-founded trees
• Autostability of automatic representations of well-orders and lower-rank linear orders
• Structures without scattered-automatic presentation
• Tree-automatic well-founded trees

Cited in

(6)

• Isomorphisms of scattered automatic linear orders
• Tree-automatic scattered linear orders
• Automatic linear orders and trees
• Pumping for ordinal-automatic structures1
• Tree-automatic well-founded trees
• Tree-automatic well-founded trees

This page was built for publication: The rank of tree-automatic linear orderings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2957918)