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.

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].

DOI : 10.1051/ita:2003016
Classification : 68Q45, 03D05, 03D55, 03E15
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] 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 ω-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 ω-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 ω-Languages. J. Inform. Process. Cybernetics EIK 22 (1986) 219-241. | MR | Zbl

[23] L. Staiger, ω-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

Cité par Sources :