Undecidability of topological and arithmetical properties of infinitary rational relations

Olivier Finkel

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2003)

  • Volume: 37, Issue: 2, page 115-126
  • ISSN: 0988-3754

Abstract

top
We prove that for every countable ordinal α one cannot decide whether a given infinitary rational relation is in the Borel class Σ α 0 (respectively Π α 0 ). Furthermore one cannot decide whether a given infinitary rational relation is a Borel set or a Σ 1 1 -complete set. We prove some recursive analogues to these properties. In particular one cannot decide whether an infinitary rational relation is an arithmetical set. We then deduce from the proof of these results some other ones, like: one cannot decide whether the complement of an infinitary rational relation is also an infinitary rational relation.

How to cite

top

Finkel, Olivier. "Undecidability of topological and arithmetical properties of infinitary rational relations." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 37.2 (2003): 115-126. <http://eudml.org/doc/244943>.

@article{Finkel2003,
abstract = {We prove that for every countable ordinal $\alpha $ one cannot decide whether a given infinitary rational relation is in the Borel class $\{\bf \Sigma _\{\alpha \}^0\}$ (respectively $\{\bf \Pi _\{\alpha \}^0\}$). Furthermore one cannot decide whether a given infinitary rational relation is a Borel set or a $\{\bf \Sigma _\{1\}^1\}$-complete set. We prove some recursive analogues to these properties. In particular one cannot decide whether an infinitary rational relation is an arithmetical set. We then deduce from the proof of these results some other ones, like: one cannot decide whether the complement of an infinitary rational relation is also an infinitary rational relation.},
author = {Finkel, Olivier},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {infinitary rational relations; topological properties; Borel and analytic sets; arithmetical properties; decision problems},
language = {eng},
number = {2},
pages = {115-126},
publisher = {EDP-Sciences},
title = {Undecidability of topological and arithmetical properties of infinitary rational relations},
url = {http://eudml.org/doc/244943},
volume = {37},
year = {2003},
}

TY - JOUR
AU - Finkel, Olivier
TI - Undecidability of topological and arithmetical properties of infinitary rational relations
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 2003
PB - EDP-Sciences
VL - 37
IS - 2
SP - 115
EP - 126
AB - We prove that for every countable ordinal $\alpha $ one cannot decide whether a given infinitary rational relation is in the Borel class ${\bf \Sigma _{\alpha }^0}$ (respectively ${\bf \Pi _{\alpha }^0}$). Furthermore one cannot decide whether a given infinitary rational relation is a Borel set or a ${\bf \Sigma _{1}^1}$-complete set. We prove some recursive analogues to these properties. In particular one cannot decide whether an infinitary rational relation is an arithmetical set. We then deduce from the proof of these results some other ones, like: one cannot decide whether the complement of an infinitary rational relation is also an infinitary rational relation.
LA - eng
KW - infinitary rational relations; topological properties; Borel and analytic sets; arithmetical properties; decision problems
UR - http://eudml.org/doc/244943
ER -

References

top
  1. [1] M.-P. Béal, O. Carton, C. Prieur and J. Sakarovitch, Squaring Transducers: An Efficient Procedure for Deciding Functionality and Sequentiality of Transducers, in Proc. of LATIN 2000, edited by G. Gonnet, D. Panario and A. Viola. Springer, Lect. Notes Comput. Sci. 1776 (2000) 397-406. Zbl0957.03046
  2. [2] J. Berstel, Transductions and Context Free Languages. Teubner Verlag (1979). Zbl0424.68040MR549481
  3. [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. Zbl0147.25103MR183636
  4. [4] C. 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.94022MR504457
  5. [5] C. 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.68107MR1719021
  6. [6] O. Finkel, On the Topological Complexity of Infinitary Rational Relations. Theoret. Informatics Appl. 37 (2003) 105-113. Zbl1112.03313MR2015686
  7. [7] O. Finkel, On Infinitary Rational Relations and Borel Sets, in Proc. of the Fourth International Conference on Discrete Mathematics and Theoretical Computer Science DMTCS’03, 7-12 July 2003, Dijon, France. Springer, Lect. Notes Comput. Sci. (to appear). Zbl1040.03033
  8. [8] C. Frougny and J. Sakarovitch, Synchronized Relations of Finite and Infinite Words. Theoret. Comput. Sci. 108 (1993) 45-82. Zbl0783.68065MR1203822
  9. [9] F. Gire, Relations Rationnelles Infinitaires, Thèse de troisième cycle. Université Paris-7, France (1981). 
  10. [10] 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. Zbl0495.68063
  11. [11] F. Gire and M. Nivat, Relations Rationnelles Infinitaires. Calcolo XXI (1984) 91-125. Zbl0552.68064MR799616
  12. [12] F. Gire, Contribution à l’Étude des Langages et Relations Infinitaires, Thèse d’État. Université Paris-7, France (1986). 
  13. [13] A.S. Kechris, Classical Descriptive Set Theory. Springer-Verlag (1995). Zbl0819.04002MR1321597
  14. [14] L.H. Landweber, Decision Problems for ω -Automata. Math. Syst. Theory 3 (1969) 376-384. Zbl0182.02402MR260595
  15. [15] 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. MR1292687
  16. [16] Y.N. Moschovakis, Descriptive Set Theory. North-Holland, Amsterdam (1980). Zbl0433.03025MR561709
  17. [17] D. Perrin and J.-E. Pin, Infinite Words. Book in preparation, available from http://www.liafa.jussieu.fr/jep/InfiniteWords.html 
  18. [18] J.-E. Pin, Logic, Semigroups and Automata on Words. Ann. Math. Artificial Intelligence 16 (1996) 343-384. Zbl0860.68071MR1389853
  19. [19] C. Prieur, Fonctions Rationnelles de Mots Infinis et Continuité, Thèse de Doctorat. Université Paris-7, France (2000). 
  20. [20] C. Prieur, How to Decide Continuity of Rational Functions on Infinite Words. Theoret. Comput. Sci. 250 (2001) 71-82. Zbl0952.68076MR1795237
  21. [21] P. Simonnet, Automates et Théorie Descriptive, Ph.D. Thesis. Université Paris-7, France (1992). JFM48.0679.04
  22. [22] L. Staiger, Hierarchies of Recursive ω -Languages. J. Inform. Process. Cybernetics EIK 22 (1986) 219-241. Zbl0627.03024MR855527
  23. [23] L. Staiger, ω -Languages, Handbook Formal Languages, Vol. 3, edited by G. Rozenberg and A. Salomaa. Springer-Verlag, Berlin (1997). Zbl0866.68057MR1470017
  24. [24] W. Thomas, Automata on Infinite Objects, edited by J. Van Leeuwen. Elsevier, Amsterdam, Handb. Theoret. Comput. Sci. B (1990) 133-191. Zbl0900.68316MR1127189

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.