Hostname: page-component-586b7cd67f-g8jcs Total loading time: 0 Render date: 2024-11-24T12:26:15.729Z Has data issue: false hasContentIssue false
  • English
  • Français

On the Topological Complexity of Infinitary Rational Relations

Published online by Cambridge University Press:  15 November 2003

Olivier Finkel
Olivier Finkel*
Affiliation:
Équipe de Logique Mathématique, U.F.R. de Mathématiques, Université Paris-7, 2 place Jussieu, 75251 Paris Cedex 05, France; [email protected].
Get access

Abstract

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

Keywords

Infinitary rational relationstopological propertiesBorel and analytic sets.
Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 37 , Issue 2 , April 2003 , pp. 105 - 113
Copyright
© EDP Sciences, 2003

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

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.
J. Berstel, Transductions and Context Free Languages. Teubner Verlag (1979).
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.
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. CrossRef
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.
Duparc, J., Finkel, O. and Ressayre, J.-P., Computer Science and the Fine Structure of Borel Sets. Theoret. Comput. Sci. 257 (2001) 85-105. CrossRef
Engelfriet, J. and Hoogeboom, H.J., X-Automata on ω-Words. Theoret. Comput. Sci. 110 (1993) 1-51. CrossRef
F. Gire, Relations Rationnelles Infinitaires, Thèse de troisième cycle, Université Paris-7, France (1981).
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.
F. Gire and M. Nivat, Relations Rationnelles Infinitaires. Calcolo XXI (1984) 91-125.
A.S. Kechris, Classical Descriptive Set Theory. Springer-Verlag (1995).
K. Kuratowski, Topology. Academic Press, New York (1966).
Landweber, L.H., Decision Problems for ω-Automata. Math. Syst. Theory 3 (1969) 376-384. CrossRef
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.
Y.N. Moschovakis, Descriptive Set Theory. North-Holland, Amsterdam (1980).
D. Niwinski, An Example of Non Borel Set of Infinite Trees Recognizable by a Rabin Automaton, in Polish, Manuscript. University of Warsaw (1985).
D. Perrin and J.-E. Pin, Infinite Words, Book in preparation, available from http://www.liafa.jussieu.fr/jep/InfiniteWords.html
Pin, J.-E., Logic, Semigroups and Automata on Words. Ann. Math. Artificial Intelligence 16 (1996) 343-384. CrossRef
C. Prieur, Fonctions Rationnelles de Mots Infinis et Continuité, Thèse de Doctorat, Université Paris-7, France (2000).
P. Simonnet, Automates et Théorie Descriptive, Ph.D. thesis, Université Paris-7, France (1992).
Simonnet, P., Automate d'Arbres Infinis et Choix Borélien. C. R. Acad. Sci. Paris Sér. I Math. 316 (1993) 97-100.
Staiger, L., Hierarchies of Recursive ω-Languages. J. Inform. Process. Cybernetics EIK 22 (1986) 219-241.
L. Staiger, ω-Languages, Handbook of Formal languages, Vol. 3, edited by G. Rozenberg and A. Salomaa. Springer-Verlag, Berlin (1997).
W. Thomas, Automata on Infinite Objects, edited by J. Van Leeuwen. Elsevier, Amsterdam, Handb. Theoret. Comput. Sci. B (1990) 133-191.