On automatic partial orders
- 22 December 2003
- proceedings article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 6, 168-177
- https://doi.org/10.1109/lics.2003.1210056
Abstract
We investigate partial orders that are computable, in a precisesense, by finite automata. Our emphasis is on treesand linear orders. We study the relationship between automaticlinear orders and trees in terms of rank functions thatare versions of Cantor-Bendixson rank. We prove that automaticlinear orders and automatic trees have finite rank.As an application we provide a procedure for deciding theisomorphism problem for automatic ordinals. We also investigatethe complexity and definability of infinite paths inautomatic trees. In particular, we show that every infinitepath in an automatic tree with countably many infinite pathsis a regular language.Keywords
This publication has 7 references indexed in Scilit:
- Finite Presentations of Infinite Structures: Automata and InterpretationsTheory of Computing Systems, 2004
- Some results on automatic structuresPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Automatic structuresPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2000
- Classical Descriptive Set TheoryPublished by Springer Nature ,1995
- Automatic presentations of structuresPublished by Springer Nature ,1995
- Word Processing in GroupsPublished by Taylor & Francis ,1992
- Sets recognized by n-tape automataJournal of Algebra, 1969