On the Topological Complexity of Infinitary Rational Relations

Olivier Finkel

RAIRO - Theoretical Informatics and Applications (2010)

  • Volume: 37, Issue: 2, page 105-113
  • ISSN: 0988-3754

Abstract

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

How to cite

top

Finkel, Olivier. "On the Topological Complexity of Infinitary Rational Relations ." RAIRO - Theoretical Informatics and Applications 37.2 (2010): 105-113. <http://eudml.org/doc/92716>.

@article{Finkel2010,
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]. },
author = {Finkel, Olivier},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Infinitary rational relations; topological properties; Borel and analytic sets.},
language = {eng},
month = {3},
number = {2},
pages = {105-113},
publisher = {EDP Sciences},
title = {On the Topological Complexity of Infinitary Rational Relations },
url = {http://eudml.org/doc/92716},
volume = {37},
year = {2010},
}

TY - JOUR
AU - Finkel, Olivier
TI - On the Topological Complexity of Infinitary Rational Relations
JO - RAIRO - Theoretical Informatics and Applications
DA - 2010/3//
PB - EDP Sciences
VL - 37
IS - 2
SP - 105
EP - 113
AB - 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].
LA - eng
KW - Infinitary rational relations; topological properties; Borel and analytic sets.
UR - http://eudml.org/doc/92716
ER -

References

top
  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. J. Berstel, Transductions and Context Free Languages. Teubner Verlag (1979).  
  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.  
  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.94022
  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.68107
  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.03044
  7. J. Engelfriet and H.J. Hoogeboom, X-Automata on ω-Words. Theoret. Comput. Sci.110 (1993) 1-51.  
  8. F. Gire, Relations Rationnelles Infinitaires, Thèse de troisième cycle, Université Paris-7, France (1981).  Zbl0552.68064
  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.  
  10. F. Gire and M. Nivat, Relations Rationnelles Infinitaires. Calcolo XXI (1984) 91-125.  Zbl0552.68064
  11. A.S. Kechris, Classical Descriptive Set Theory. Springer-Verlag (1995).  Zbl0819.04002
  12. K. Kuratowski, Topology. Academic Press, New York (1966).  
  13. L.H. Landweber, Decision Problems for ω-Automata. Math. Syst. Theory3 (1969) 376-384.  Zbl0182.02402
  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.  
  15. Y.N. Moschovakis, Descriptive Set Theory. North-Holland, Amsterdam (1980).  
  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 Intelligence16 (1996) 343-384.  
  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).  
  21. P. Simonnet, Automate d'Arbres Infinis et Choix Borélien. C. R. Acad. Sci. Paris Sér. I Math.316 (1993) 97-100.  
  22. L. Staiger, Hierarchies of Recursive ω-Languages. J. Inform. Process. Cybernetics EIK22 (1986) 219-241.  Zbl0627.03024
  23. L. Staiger, ω-Languages, Handbook of Formal languages, Vol. 3, edited by G. Rozenberg and A. Salomaa. Springer-Verlag, Berlin (1997).  
  24. W. Thomas, Automata on Infinite Objects, edited by J. Van Leeuwen. Elsevier, Amsterdam, Handb. Theoret. Comput. Sci. B (1990) 133-191.  Zbl0900.68316

Citations in EuDML Documents

top
  1. Olivier Finkel, Undecidability of Topological and Arithmetical Properties of Infinitary Rational Relations
  2. Olivier Finkel, Undecidability of topological and arithmetical properties of infinitary rational relations
  3. Benoit Cagnard, Pierre Simonnet, Automata, Borel functions and real numbers in Pisot base
  4. Olivier Carton, Olivier Finkel, Pierre Simonnet, On the continuity set of an Omega rational function
  5. Olivier Finkel, Highly Undecidable Problems For Infinite Computations

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.