Please use this identifier to cite or link to this item: https://doi.org/10.1145/1094622.1094625
Title: Automatic linear orders and trees
Authors: Khoussainov, B.
Rubin, S.
Stephan, F. 
Keywords: Automatic structures
Linear orders
Trees
Issue Date: 2005
Source: Khoussainov, B.,Rubin, S.,Stephan, F. (2005). Automatic linear orders and trees. ACM Transactions on Computational Logic 6 (4) : 675-700. ScholarBank@NUS Repository. https://doi.org/10.1145/1094622.1094625
Abstract: We investigate partial orders that are computable, in a precise sense, by finite automata. Our emphasis is on trees and linear orders. We study the relationship between automatic linear orders and trees in terms of rank functions that are related to Cantor-Bendixson rank. We prove that automatic linear orders and automatic trees have finite rank. As an application we provide a procedure for deciding the isomorphism problem for automatic ordinals. We also investigate the complexity and definability of infinite paths in automatic trees. In particular, we show that every infinite path in an automatic tree with countably many infinite paths is a regular language. © 2005 ACM.
Source Title: ACM Transactions on Computational Logic
URI: http://scholarbank.nus.edu.sg/handle/10635/40491
ISSN: 15293785
DOI: 10.1145/1094622.1094625
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

40
checked on Dec 11, 2017

Page view(s)

61
checked on Dec 9, 2017

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.