Undecidability of topological and arithmetical properties of infinitary rational relations
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 37 (2003) no. 2, pp. 115-126.

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.

DOI : https://doi.org/10.1051/ita:2003013
Classification : 68Q45,  03D05,  03D55,  03E15
Mots clés : infinitary rational relations, topological properties, Borel and analytic sets, arithmetical properties, decision problems
@article{ITA_2003__37_2_115_0,
     author = {Finkel, Olivier},
     title = {Undecidability of topological and arithmetical properties of infinitary rational relations},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {115--126},
     publisher = {EDP-Sciences},
     volume = {37},
     number = {2},
     year = {2003},
     doi = {10.1051/ita:2003013},
     zbl = {1112.03312},
     mrnumber = {2015687},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ita:2003013/}
}
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
DA  - 2003///
SP  - 115
EP  - 126
VL  - 37
IS  - 2
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita:2003013/
UR  - https://zbmath.org/?q=an%3A1112.03312
UR  - https://www.ams.org/mathscinet-getitem?mr=2015687
UR  - https://doi.org/10.1051/ita:2003013
DO  - 10.1051/ita:2003013
LA  - en
ID  - ITA_2003__37_2_115_0
ER  - 
Finkel, Olivier. Undecidability of topological and arithmetical properties of infinitary rational relations. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 37 (2003) no. 2, pp. 115-126. doi : 10.1051/ita:2003013. http://www.numdam.org/articles/10.1051/ita:2003013/

[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. | Zbl 0957.03046

[2] J. Berstel, Transductions and Context Free Languages. Teubner Verlag (1979). | MR 549481 | Zbl 0424.68040

[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 183636 | Zbl 0147.25103

[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. | MR 504457 | Zbl 0376.94022

[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. | MR 1719021 | Zbl 0944.68107

[6] O. Finkel, On the Topological Complexity of Infinitary Rational Relations. Theoret. Informatics Appl. 37 (2003) 105-113. | Numdam | MR 2015686 | Zbl 1112.03313

[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). | Zbl 1040.03033

[8] C. Frougny and J. Sakarovitch, Synchronized Relations of Finite and Infinite Words. Theoret. Comput. Sci. 108 (1993) 45-82. | MR 1203822 | Zbl 0783.68065

[9] F. Gire, Relations Rationnelles Infinitaires, Thèse de troisième cycle. Université Paris-7, France (1981).

[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. | Zbl 0495.68063

[11] F. Gire and M. Nivat, Relations Rationnelles Infinitaires. Calcolo XXI (1984) 91-125. | MR 799616 | Zbl 0552.68064

[12] F. Gire, Contribution à l'Étude des Langages et Relations Infinitaires, Thèse d'État. Université Paris-7, France (1986).

[13] A.S. Kechris, Classical Descriptive Set Theory. Springer-Verlag (1995). | MR 1321597 | Zbl 0819.04002

[14] L.H. Landweber, Decision Problems for ω-Automata. Math. Syst. Theory 3 (1969) 376-384. | MR 260595 | Zbl 0182.02402

[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. | MR 1292687

[16] Y.N. Moschovakis, Descriptive Set Theory. North-Holland, Amsterdam (1980). | MR 561709 | Zbl 0433.03025

[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 1389853 | Zbl 0860.68071

[19] C. Prieur, Fonctions Rationnelles de Mots Infinis et Continuité, Thèse de Doctorat. Université Paris-7, France (2000).

[20] C. Prieur, How to Decide Continuity of Rational Functions on Infinite Words. Theoret. Comput. Sci. 250 (2001) 71-82. | MR 1795237 | Zbl 0952.68076

[21] P. Simonnet, Automates et Théorie Descriptive, Ph.D. Thesis. Université Paris-7, France (1992). | JFM 48.0679.04

[22] L. Staiger, Hierarchies of Recursive ω-Languages. J. Inform. Process. Cybernetics EIK 22 (1986) 219-241. | MR 855527 | Zbl 0627.03024

[23] L. Staiger, ω-Languages, Handbook Formal Languages, Vol. 3, edited by G. Rozenberg and A. Salomaa. Springer-Verlag, Berlin (1997). | MR 1470017 | Zbl 0866.68057

[24] W. Thomas, Automata on Infinite Objects, edited by J. Van Leeuwen. Elsevier, Amsterdam, Handb. Theoret. Comput. Sci. B (1990) 133-191. | MR 1127189 | Zbl 0900.68316

Cité par Sources :