The Wadge-Wagner hierarchy of ω-rational sets

1. Jorge Almeida. Finite Semigroups and Universal Algebra. World Scientific, 1994.

   Google Scholar 

2. Rana Barua. The Hausdorff-Kuratowski hierarchy of ω-regular languages and a hierarchy of Muller automata. Theoretical Computer Science, 96:345–360, 1992.

   Article  Google Scholar 

3. Nicolas Bedon. Automata, semigroups and recognizability of words on ordinals. IGM report 96-5, to appear in International Journal of Algebra and Computation.

   Google Scholar 

4. Olivier Carton. Mots infinis, ω-semigroupes et Topologie. Thèse, Université Paris 7, 1993. Report LITP-TH 93-08.

   Google Scholar 

5. Olivier Carton and Dominique Perrin. The Wagner hierarchy of ω-rational sets. To appear in International journal of algebra and computation.

   Google Scholar 

6. Olivier Carton and Dominique Perrin. Chains and superchains in ω-semigroups. In Jorge Almeida, Grancinda Gomes, and Pedro Silva, editors, Semigroups, Automata and Languages, pages 17–28. World Scientific, 1994.

   Google Scholar 

7. Olivier Carton and Dominique Perrin. Chains and superchains for ω-rational sets, automata and semigroups. International journal of algebra and computation, 1997. to appear.

   Google Scholar 

8. John M. Howie. Fundamentals of Semigroup Theory. Oxford University Press, 1995.

   Google Scholar 

9. Micheal Kaminski. A classification of ω-regular languages. Theoretical Computer Science, 36:217–229, 1985.

   Article  Google Scholar 

10. Alexander S. Kechris. Classical Descriptive Set Theory, volume 156 of Graduate texts in mathematics. 1995.

    Google Scholar 

11. Sriram C. Krishnan, Anuj Puri, and Robert K. Brayton. Structural complexity of ω-languages. In STACS '95, volume 900 of Lecture Notes in Computer Science, pages 143–156, Berlin, 1995. Springer-Verlag.

    Google Scholar 

12. Lawrence H. Landweber. Decision problems for ω-automata. Mathematical Systems Theory, 3:376–384, 1969.

    Article  Google Scholar 

13. Douglas Lind and Brian Marcus. An Introduction to Symbolic Dynamics and Coding. Cambridge University Press, 1995.

    Google Scholar 

14. Alain Louveau. Some results in the Wadge hierarchy of Borel sets. In A.S. Kechris et al., editor, Cabal Seminar 79-81, volume 1019 of Lecture Notes in Math., pages 28–55. Springer-Verlag, 1981.

    Google Scholar 

15. Zohar Manna and Amir Pnueli. A hierarchy of temporal properties. In Principles of Distributed Computing, pages 377–408, 1990.

    Google Scholar 

16. Dominique Perrin and Jean-Eric Pin. Infinite words. Version 1.4, Report LITP 97.04 (http://litp.ibp.fr/∼jep/Resumes/MotsInfinis.html).

    Google Scholar 

17. Dominique Perrin and Jean-Eric Pin. Semigroups and automata on infinite words. In J. Fountain and V. A. R. Gould, editors, NATO Advanced Study Institute Semi-groups, Formal Languages and Groups, pages 49–72. Kluwer academic publishers, 1995.

    Google Scholar 

18. Jean-Eric Pin. A variety theorem without complementation. Russian Mathematics (Iz. VUZ), 39:80–90, 1995.

    Google Scholar 

19. Pierre Simonnet. Automates et Théorie Descriptive. Thèse, Université Paris 7, 1992.

    Google Scholar 

20. Ludwig Staiger and Klaus Wagner. Automatentheoretische und automatenfreie Charakterisierungen topologischer Klassen regulärer Folgenmengen. Elektron. Informationsverarb. Kybernet., 10:379–392, 1974.

    Google Scholar 

21. Wolfgang Thomas. Automata on infinite objects. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science, volume B, chapter 4. Eisevier, 1990.

    Google Scholar 

22. Klaus Wagner. On ω-regular sets. Information and Control, 43:123–177, 1979.

    Article  Google Scholar 

23. Thomas Wilke. An Eilenberg theorem for ∞-languages. In ICALP '91, volume 510 of Lecture Notes in Computer Science, pages 588–599, Berlin, 1991. Springer-Verlag.

    Google Scholar 

24. Thomas Wilke. An algebraic theory for regular languages of finite and infinite words. Int. J. Alg. Comput., 3(4):447–489, 1993.

    Article  Google Scholar 

25. Thomas Wilke and Haiseung Yoo. Computing the Rabin index of a regular language of infinite words. To appear in International Journal of Algebra and Computation, 1997.

    Google Scholar 

Download references