Automatic linear orders and trees

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.

REFERENCES

• 1: Blumensath, A. 1999. Automatic structures. Diploma Thesis, RWTH Aachen.
• 2: Achim Blumensath , Erich Grädel, Automatic Structures, Proceedings of the 15th Annual IEEE Symposium on Logic in Computer Science, p.51, June 26-29, 2000
• 3: Delhommé, C. 2004. Automaticité des ordinaux et des graphes homogénes. Comput. Rend. Math. 339, 1, 5--10.
• 4: Delhommé, C. 2004. Automaticité des ordinaux et des graphes homogènes. C.R. Acad. Sci. Paris Ser. I 339, 5--10.
• 5: Eilenberg, S., Elgot, C., and Shepherdson, J. 1969. Sets recognized by n-tape automata. J. Alg. 13, 4, 447--464.
• 6: David B. A. Epstein , M. S. Paterson , G. W. Camon , D. F. Holt , S. V. Levy , W. P. Thurston, Word Processing in Groups, A. K. Peters, Ltd., Natick, MA, 1992
• 7: Hausdorff, F. 1908. Grundzüge einer theorie der geordnete mengen. Math. Ann 65, 435--505.
• 8: Hajime Ishihara , Bakhadyr Khoussainov , Sasha Rubin, Some Results on Automatic Structures, Proceedings of the 17th Annual IEEE Symposium on Logic in Computer Science, p.235, July 22-25, 2002
• 9: Kechris, A. 1995. Classical Descriptive Set Theory. Springer-Verlag, New York.
• 10: Bakhadyr Khoussainov , Anil Nerode, Automatic Presentations of Structures, Selected Papers from the International Workshop on Logical and Computational Complexity, p.367-392, October 13-16, 1994
• 11: Bakhadyr Khoussainov , Anil Nerode, Automata Theory and Its Applications, Birkhauser Boston, 2001
• 12: Bakhadyr Khoussainov , Andre Nies , Sasha Rubin , Frank Stephan, Automatic Structures: Richness and Limitations, Proceedings of the 19th Annual IEEE Symposium on Logic in Computer Science (LICS'04), p.44-53, July 13-17, 2004 [doi>10.1109/LICS.2004.11]
• 13: Bakhadyr Khoussainov , Sasha Rubin, Graphs with automatic presentations over a unary alphabet, Journal of Automata, Languages and Combinatorics, v.6 n.4, p.467-480, April 2001
• 14: Bakhadyr Khoussainov , Sasha Rubin, Automatic structures: overview and future directions, Journal of Automata, Languages and Combinatorics, v.8 n.2, p.287-301, April 2003
• 15: Khoussainov, B., Rubin, S., and Stephan, F. 2004b. Definability and regularity in automatic structures. In Proceedings of the 21st Symposium on Theoretical Aspects of Computer Science (STACS 2004). 440--451.
• 16: Kuske, D. 2003. Is Cantor's theorem automatic ? In Proceedings of the 10th International Conference on Logic for Programming Artificial Intelligence and Reasoning (LPAR 2003). 330--343.
• 17: Lohrey, M. 2003. Automatic structures of bounded degree. In Proceedings of the 10th International Conference on Logic for Programming Artificial Intelligence and Reasoning (LPAR 2003). 344--358.
• 18: Hartley Rogers, Jr., Theory of recursive functions and effective computability, MIT Press, Cambridge, MA, 1987
• 19: Rosenstein, J. 1982. Linear Orderings. Academic Press, Orlando, FL.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Automata (e.g., finite, push-down, resource-bounded)

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.3 Formal Languages
          Subjects: Classes defined by grammars or automata (e.g., context-free languages, regular sets, recursive sets)

General Terms:
Languages, Theory

Keywords:
Automatic structures, linear orders, trees