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].
Mots clés : infinitary rational relations, topological properties, Borel and analytic sets
@article{ITA_2003__37_2_105_0, author = {Finkel, Olivier}, title = {On the topological complexity of infinitary rational relations}, journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications}, pages = {105--113}, publisher = {EDP-Sciences}, volume = {37}, number = {2}, year = {2003}, doi = {10.1051/ita:2003016}, mrnumber = {2015686}, zbl = {1112.03313}, language = {en}, url = {http://www.numdam.org/articles/10.1051/ita:2003016/} }
TY - JOUR AU - Finkel, Olivier TI - On the topological complexity of infinitary rational relations JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2003 SP - 105 EP - 113 VL - 37 IS - 2 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ita:2003016/ DO - 10.1051/ita:2003016 LA - en ID - ITA_2003__37_2_105_0 ER -
%0 Journal Article %A Finkel, Olivier %T On the topological complexity of infinitary rational relations %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2003 %P 105-113 %V 37 %N 2 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ita:2003016/ %R 10.1051/ita:2003016 %G en %F ITA_2003__37_2_105_0
Finkel, Olivier. On the topological complexity of infinitary rational relations. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 37 (2003) no. 2, pp. 105-113. doi : 10.1051/ita:2003016. http://www.numdam.org/articles/10.1051/ita:2003016/
[1] 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
and ,[2] Transductions and Context Free Languages. Teubner Verlag (1979). | MR | Zbl
,[3] 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] 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] 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
and ,[6] Computer Science and the Fine Structure of Borel Sets. Theoret. Comput. Sci. 257 (2001) 85-105. | MR | Zbl
, and ,[7] X-Automata on -Words. Theoret. Comput. Sci. 110 (1993) 1-51. | MR | Zbl
and ,[8] Relations Rationnelles Infinitaires, Thèse de troisième cycle, Université Paris-7, France (1981).
,[9] 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] Relations Rationnelles Infinitaires. Calcolo XXI (1984) 91-125. | MR | Zbl
and ,[11] Classical Descriptive Set Theory. Springer-Verlag (1995). | MR | Zbl
,[12] Topology. Academic Press, New York (1966). | MR | Zbl
,[13] Decision Problems for -Automata. Math. Syst. Theory 3 (1969) 376-384. | MR | Zbl
,[14] 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
and ,[15] Descriptive Set Theory. North-Holland, Amsterdam (1980). | MR | Zbl
,[16] An Example of Non Borel Set of Infinite Trees Recognizable by a Rabin Automaton, in Polish, Manuscript. University of Warsaw (1985).
,[17] Infinite Words, Book in preparation, available from http://www.liafa.jussieu.fr/jep/InfiniteWords.html
and ,[18] Logic, Semigroups and Automata on Words. Ann. Math. Artificial Intelligence 16 (1996) 343-384. | MR | Zbl
,[19] Fonctions Rationnelles de Mots Infinis et Continuité, Thèse de Doctorat, Université Paris-7, France (2000).
,[20] Automates et Théorie Descriptive, Ph.D. thesis, Université Paris-7, France (1992). | JFM
,[21] Automate d'Arbres Infinis et Choix Borélien. C. R. Acad. Sci. Paris Sér. I Math. 316 (1993) 97-100. | Zbl
,[22] Hierarchies of Recursive -Languages. J. Inform. Process. Cybernetics EIK 22 (1986) 219-241. | MR | Zbl
,[23] -Languages, Handbook of Formal languages, Vol. 3, edited by G. Rozenberg and A. Salomaa. Springer-Verlag, Berlin (1997). | MR | Zbl
,[24] Automata on Infinite Objects, edited by J. Van Leeuwen. Elsevier, Amsterdam, Handb. Theoret. Comput. Sci. B (1990) 133-191. | MR | Zbl
,Cité par Sources :