On the topological complexity of infinitary rational relations

Finkel, Olivier

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 37 (2003) no. 2, pp. 105-113.

We prove in this paper that there exists some infinitary rational relations which are analytic but non Borel sets, giving an answer to a question of Simonnet [20].

[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. | Zbl

[2] J. Berstel, Transductions and Context Free Languages. Teubner Verlag (1979). | MR | Zbl

[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. | MR | Zbl

[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. | MR | Zbl

[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. | MR | Zbl

[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. | MR | Zbl

[7] J. Engelfriet and H.J. Hoogeboom, X-Automata on $\omega$-Words. Theoret. Comput. Sci. 110 (1993) 1-51. | MR | Zbl

[8] F. Gire, Relations Rationnelles Infinitaires, Thèse de troisième cycle, Université Paris-7, France (1981).

[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. | Zbl

[10] F. Gire and M. Nivat, Relations Rationnelles Infinitaires. Calcolo XXI (1984) 91-125. | MR | Zbl

[11] A.S. Kechris, Classical Descriptive Set Theory. Springer-Verlag (1995). | MR | Zbl

[12] K. Kuratowski, Topology. Academic Press, New York (1966). | MR | Zbl

[13] L.H. Landweber, Decision Problems for $\omega$-Automata. Math. Syst. Theory 3 (1969) 376-384. | MR | Zbl

[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. | MR

[15] Y.N. Moschovakis, Descriptive Set Theory. North-Holland, Amsterdam (1980). | MR | Zbl

[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] D. Perrin and J.-E. Pin, Infinite Words, Book in preparation, available from http://www.liafa.jussieu.fr/jep/InfiniteWords.html

[18] J.-E. Pin, Logic, Semigroups and Automata on Words. Ann. Math. Artificial Intelligence 16 (1996) 343-384. | MR | Zbl

[19] C. Prieur, Fonctions Rationnelles de Mots Infinis et Continuité, Thèse de Doctorat, Université Paris-7, France (2000).

[20] P. Simonnet, Automates et Théorie Descriptive, Ph.D. thesis, Université Paris-7, France (1992). | JFM

[21] P. Simonnet, Automate d'Arbres Infinis et Choix Borélien. C. R. Acad. Sci. Paris Sér. I Math. 316 (1993) 97-100. | Zbl

[22] L. Staiger, Hierarchies of Recursive $\omega$-Languages. J. Inform. Process. Cybernetics EIK 22 (1986) 219-241. | MR | Zbl

[23] L. Staiger, $\omega$-Languages, Handbook of Formal languages, Vol. 3, edited by G. Rozenberg and A. Salomaa. Springer-Verlag, Berlin (1997). | MR | Zbl

[24] W. Thomas, Automata on Infinite Objects, edited by J. Van Leeuwen. Elsevier, Amsterdam, Handb. Theoret. Comput. Sci. B (1990) 133-191. | MR | Zbl