Automata on Linear Orderings

1. E. Asarin. Equations on timed languages. In T. Henzinger and S. Sastry, editors, Hybrid Systems: Computation and Control, number 1386 in Lect. Notes in Comput. Sci., pages 1–12, 1998.

   Google Scholar 

2. E. Asarin, P. Caspi, and O. Maler. A Kleene theorem for timed automata. In Proceedings, Twelth Annual IEEE Symposium on Logic in Computer Science, pages 160–171, 1997.

   Google Scholar 

3. N. Bedon and O. Carton. An Eilenberg theorem for words on countable ordinals. In Cláudio 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.

   Google Scholar 

4. B. Bérard and C. Picaronny. Accepting Zeno words without making time stand still. In Mathematical Foundations of Computer Science 1997, volume 1295 of Lect. Notes in Comput. Sci., pages 149–158, 1997.

   Google Scholar 

5. P. Bouyer and A. Petit. A Kleene/Büchi-like theorem for clock languages. J. of Automata, Languages and Combinatorics, 2001. To appear.

   Google Scholar 

6. V. Bruyère and O. Carton. Automata on linear orderings. Technical Report 2000-12, Institut Gaspard Monge, 2000. Submitted.

   Google Scholar 

7. V. Bruyère and O. Carton. Automata on linear orderings. In Jiří Sgall, Aleš Pultr, and Petr Kolman, editors, MFCS’2001, volume 2136 of Lect. Notes in Comput. Sci., pages 236–247, 2001.

   Google Scholar 

8. V. Bruyère and O. Carton. Hierarchy among automata on linear orderings. In R. Baeza-Yates, U. Montanari, and N. Santoro, editors, TCS’2002/IFIP’2002, pages 107–118. Kluwer Academic Publishers, 2002.

   Google Scholar 

9. J. R. Büchi. Weak second-order arithmetic and finite automata. Z. Math. Logik und grundl. Math., 6:66–92, 1960.

   Article  MATH  Google Scholar 

10. J. R. Büchi. On a decision method in the restricted second-order arithmetic. In Proc. Int. Congress Logic, Methodology and Philosophy of science, Berkeley 1960, pages 1–11. Stanford University Press, 1962.

    Google Scholar 

11. J. R. Büchi. Transfinite 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.

    Google Scholar 

12. Y. Choueka. Finite automata, definable sets, and regular expressions over ωⁿ-tapes. J. Comput. System Sci., 17(1):81–97, 1978.

    Article  MATH  MathSciNet  Google Scholar 

13. B. Courcelle. Frontiers of infinite trees. RAIRO Theoretical Informatics, 12(4):319–337, 1978.

    MATH  MathSciNet  Google Scholar 

14. D. Girault-Beauquier. Bilimites de langages reconnaissables. Theoret. Comput. Sci., 33(2–3):335–342, 1984.

    Article  MATH  MathSciNet  Google Scholar 

15. M. R. Hansen, P. K. Pandya, and Z. Chaochen. Finite divergence. Theoret. Comput. Sci., 138(1):113–139, 1995.

    Article  MATH  MathSciNet  Google Scholar 

16. S. Heilbrunner. An algorithm for the solution of fixed-point equations for infinite words. RAIRO Theoretical Informatics, 14(2):131–141, 1980.

    MATH  MathSciNet  Google Scholar 

17. S. C. Kleene. Representation of events in nerve nets and finite automata. In C.E. Shannon, editor, Automata studies, pages 3–41. Princeton University Press, Princeton, 1956.

    Google Scholar 

18. M. Nivat and D. Perrin. Ensembles reconnaissables de mots bi-infinis. In Proceedings of the Fourteenth Annual ACM Symposium on Theory of Computing, pages 47–59, 1982.

    Google Scholar 

19. D. Perrin. Finite automata. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science, volume B, chapter 1, pages 1–57. Elsevier, 1990.

    Google Scholar 

20. J. G. Rosenstein. Linear Orderings. Academic Press, New York, 1982.

    MATH  Google Scholar 

21. S. Shelah. The monadic theory of order. Annals of Mathematics, 102:379–419, 1975.

    Article  MathSciNet  Google Scholar 

22. W. Thomas. On frontiers of regular sets. RAIRO Theoretical Informatics, 20:371–381, 1986.

    MATH  Google Scholar 

23. W. Thomas. Automata on infinite objects. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science, volume B, chapter 4, pages 133–191. Elsevier, 1990.

    Google Scholar 

24. W. Thomas. Ehrenfeucht games, the composition method, and the monadic theory of ordinal words. In Structures in Logic and Computer Science, A Selection of Essays in Honor of A. Ehrenfeucht, number 1261 in Lect. Notes in Comput. Sci., pages 118–143. Springer-Verlag, 1997.

    Google Scholar 

25. J. Wojciechowski. Finite automata on transfinite sequences and regular expressions. Fundamenta Informaticæ, 8(3–4):379–396, 1985.

    MATH  MathSciNet  Google Scholar 

Download references