Hierarchy among Automata on Linear Orderings

Article English OPEN
Bruyère , Véronique ; Carton , Olivier (2005)
  • Publisher: Springer Verlag
  • Subject: [ INFO.INFO-DS ] Computer Science [cs]/Data Structures and Algorithms [cs.DS]
    acm: TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES | ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION
    arxiv: Computer Science::Formal Languages and Automata Theory

In a preceding paper, automata and rational expressions have been introduced for words indexed by linear orderings, together with a Kleene-like theorem. We here pursue this work by proposing a hierarchy among the rational sets. Each class of the hierarchy is defined by a subset of the rational operations that can be used. We then characterize any class by an appropriate class of automata, leading to a Kleene theorem inside the class. A characterization by particular classes of orderings is also given.
  • References (23)
    23 references, page 1 of 3

    [1] N. Bedon. Langages reconnaissables de mots indexes par des ordinaux. These de doctorat, Universite de Marne-la-Vallee, 1998.

    [2] N. Bedon and O. Carton. An Eilenberg theorem for words on countable ordinals. In Claudio L. Lucchesi and Arnaldo V. Moura, editors, Latin'98: Theoretical Informatics, volume 1380 of Lect. Notes in Comput. Sci., pages 53{64. Springer-Verlag, 1998.

    [3] S. L. Bloom and Ch. Cho rut. Long words: the theory of concatenation and omega-power. Theoret. Comput. Sci., 259:533{548, 2001.

    [4] S. L. Bloom and Z. Esik. Axiomatizing omega and omega-op powers of words. RAIRO Theoretical informatics, 38:3{17, 2004.

    [5] V. Bruyere and O. Carton. Automata on linear orderings. Technical Report 2000-12, Institut Gaspard Monge, 2000. Submitted.

    [6] V. Bruyere and O. Carton. Automata on linear orderings. In J. Sgall, A. Pultr, and P. Kolman, editors, MFCS'2001, volume 2136 of Lect. Notes in Comput. Sci., pages 236{247, 2001.

    [7] V. Bruyere and O. Carton. Hierarchy among automata on linear orderings. In R. Baeza-Yates, U. Montanari, and N. Santoro, editors, Foundation of Information technology in the era of network and mobile computing, pages 107{118. Kluwer Academic Publishers, 2002. TCS'2002/IFIP'2002.

    [8] V. Bruyere, O. Carton, and G. Senizergues. Tree automata and automata on linear orderings. In Tero Harju and Juhani Karhumaki, editors, WORDS'2003, volume 27 of TUCS General Publication, pages 222{231, 2003.

    [9] J. R. Buchi. Weak second-order arithmetic and nite automata. Z. Math. Logik und grundl. Math., 6:66{92, 1960.

    [10] J. R. Buchi. Trans nite automata recursions and weak second order theory of ordinals. In Proc. Int. Congress Logic, Methodology, and Philosophy of Science, Jerusalem 1964, pages 2{23. North Holland, 1965.

  • Metrics
    No metrics available
Share - Bookmark