Eighteenth Annual IEEE Symposium on

Logic in Computer Science (LICS 2003)

Paper: On Automatic Partial Orders (at LICS 2003)

Authors: Bakhadyr Khoussainov Sasha Rubin Frank Stephan


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 versions of 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.


    author = 	 {Bakhadyr Khoussainov and Sasha Rubin and Frank Stephan},
    title = 	 {On Automatic Partial Orders},
    booktitle =  {Proceedings of the Eighteenth Annual IEEE Symp. on Logic in Computer Science, {LICS} 2003},
    year =	 2003,
    editor =	 {Phokion G. Kolaitis},
    month =	 {June}, 
    pages =      {168--177},
    location =   {Ottawa, Canada}, 
    publisher =	 {IEEE Computer Society Press}