On the topological complexity of infinitary rational relations

 Access to full text

 Full (PDF)

1. [1] M.-P. Béal and O. Carton, Determinization of Transducers over Infinite Words, in ICALP’2000, edited by U. Montanari et al. Springer, Lect. Notes Comput. Sci. 1853 (2000) 561-570. Zbl0973.68113
2. [2] J. Berstel, Transductions and Context Free Languages. Teubner Verlag (1979). Zbl0424.68040MR549481
3. [3] J.R. Büchi, On a Decision Method in Restricted Second Order Arithmetic, Logic Methodology and Philosophy of Science, in Proc. 1960 Int. Congr. Stanford University Press (1962) 1-11. Zbl0147.25103MR183636
4. [4] Ch. Choffrut, Une Caractérisation des Fonctions Séquentielles et des Fonctions Sous-Séquentielles en tant que Relations Rationnelles. Theoret. Comput. Sci. 5 (1977) 325-338. Zbl0376.94022MR504457
5. [5] Ch. Choffrut and S. Grigorieff, Uniformization of Rational Relations, Jewels are Forever, edited by J. Karhumäki, H. Maurer, G. Paun and G. Rozenberg. Springer (1999) 59-71. Zbl0944.68107MR1719021
6. [6] J. Duparc, O. Finkel and J.-P. Ressayre, Computer Science and the Fine Structure of Borel Sets. Theoret. Comput. Sci. 257 (2001) 85-105. Zbl0971.03044MR1824849
7. [7] J. Engelfriet and H.J. Hoogeboom, X-Automata on $\omega$-Words. Theoret. Comput. Sci. 110 (1993) 1-51. Zbl0777.68058MR1208658
8. [8] F. Gire, Relations Rationnelles Infinitaires, Thèse de troisième cycle, Université Paris-7, France (1981). 
9. [9] F. Gire, Une Extension aux Mots Infinis de la Notion de Transduction Rationnelle, in 6th GI Conf. Springer, Lect. Notes Comput. Sci. 145 (1983) 123-139. Zbl0495.68063
10. [10] F. Gire and M. Nivat, Relations Rationnelles Infinitaires. Calcolo XXI (1984) 91-125. Zbl0552.68064MR799616
11. [11] A.S. Kechris, Classical Descriptive Set Theory. Springer-Verlag (1995). Zbl0819.04002MR1321597
12. [12] K. Kuratowski, Topology. Academic Press, New York (1966). Zbl0158.40802MR217751
13. [13] L.H. Landweber, Decision Problems for $\omega$-Automata. Math. Syst. Theory 3 (1969) 376-384. Zbl0182.02402MR260595
14. [14] H. Lescow and W. Thomas, Logical Specifications of Infinite Computations, in A Decade of Concurrency, edited by J.W. de Bakker et al. Springer, Lect. Notes Comput. Sci. 803 (1994) 583-621. MR1292687
15. [15] Y.N. Moschovakis, Descriptive Set Theory. North-Holland, Amsterdam (1980). Zbl0433.03025MR561709
16. [16] D. Niwinski, An Example of Non Borel Set of Infinite Trees Recognizable by a Rabin Automaton, in Polish, Manuscript. University of Warsaw (1985). 
17. [17] D. Perrin and J.-E. Pin, Infinite Words, Book in preparation, available from http://www.liafa.jussieu.fr/jep/InfiniteWords.html 
18. [18] J.-E. Pin, Logic, Semigroups and Automata on Words. Ann. Math. Artificial Intelligence 16 (1996) 343-384. Zbl0860.68071MR1389853
19. [19] C. Prieur, Fonctions Rationnelles de Mots Infinis et Continuité, Thèse de Doctorat, Université Paris-7, France (2000). 
20. [20] P. Simonnet, Automates et Théorie Descriptive, Ph.D. thesis, Université Paris-7, France (1992). JFM48.0679.04
21. [21] P. Simonnet, Automate d’Arbres Infinis et Choix Borélien. C. R. Acad. Sci. Paris Sér. I Math. 316 (1993) 97-100. Zbl0791.68112
22. [22] L. Staiger, Hierarchies of Recursive $\omega$-Languages. J. Inform. Process. Cybernetics EIK 22 (1986) 219-241. Zbl0627.03024MR855527
23. [23] L. Staiger, $\omega$-Languages, Handbook of Formal languages, Vol. 3, edited by G. Rozenberg and A. Salomaa. Springer-Verlag, Berlin (1997). Zbl0866.68057MR1470017
24. [24] W. Thomas, Automata on Infinite Objects, edited by J. Van Leeuwen. Elsevier, Amsterdam, Handb. Theoret. Comput. Sci. B (1990) 133-191. Zbl0900.68316MR1127189