# Undecidability of Topological and Arithmetical Properties of Infinitary Rational Relations

RAIRO - Theoretical Informatics and Applications (2010)

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

## Access Full Article

top## Abstract

top## How to cite

topFinkel, Olivier. "Undecidability of Topological and Arithmetical Properties of Infinitary Rational Relations." RAIRO - Theoretical Informatics and Applications 37.2 (2010): 115-126. <http://eudml.org/doc/92717>.

@article{Finkel2010,

abstract = {
We prove that for every countable ordinal α 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},

keywords = {Infinitary rational relations; topological properties; Borel and
analytic sets; arithmetical properties; decision problems.},

language = {eng},

month = {3},

number = {2},

pages = {115-126},

publisher = {EDP Sciences},

title = {Undecidability of Topological and Arithmetical Properties of Infinitary Rational Relations},

url = {http://eudml.org/doc/92717},

volume = {37},

year = {2010},

}

TY - JOUR

AU - Finkel, Olivier

TI - Undecidability of Topological and Arithmetical Properties of Infinitary Rational Relations

JO - RAIRO - Theoretical Informatics and Applications

DA - 2010/3//

PB - EDP Sciences

VL - 37

IS - 2

SP - 115

EP - 126

AB -
We prove that for every countable ordinal α 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/92717

ER -

## References

top- 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
- 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.
- 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.94022
- 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.68107
- O. Finkel, On the Topological Complexity of Infinitary Rational Relations. Theoret. Informatics Appl.37 (2003) 105-113. Zbl1112.03313
- 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).
- C. Frougny and J. Sakarovitch, Synchronized Relations of Finite and Infinite Words. Theoret. Comput. Sci.108 (1993) 45-82. Zbl0783.68065
- 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. Zbl0552.68064
- F. Gire, Contribution à l'Étude des Langages et Relations Infinitaires, Thèse d'État. Université Paris-7, France (1986).
- A.S. Kechris, Classical Descriptive Set Theory. Springer-Verlag (1995). Zbl0819.04002
- L.H. Landweber, Decision Problems for ω-Automata. Math. Syst. Theory3 (1969) 376-384. Zbl0182.02402
- 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. Perrin and J.-E. Pin, Infinite Words. Book in preparation, available from http://www.liafa.jussieu.fr/jep/InfiniteWords.html
- J.-E. Pin, Logic, Semigroups and Automata on Words. Ann. Math. Artificial Intelligence16 (1996) 343-384.
- C. Prieur, Fonctions Rationnelles de Mots Infinis et Continuité, Thèse de Doctorat. Université Paris-7, France (2000).
- C. Prieur, How to Decide Continuity of Rational Functions on Infinite Words. Theoret. Comput. Sci.250 (2001) 71-82. Zbl0952.68076
- P. Simonnet, Automates et Théorie Descriptive, Ph.D. Thesis. Université Paris-7, France (1992).
- L. Staiger, Hierarchies of Recursive ω-Languages. J. Inform. Process. Cybernetics EIK22 (1986) 219-241. Zbl0627.03024
- L. Staiger, ω-Languages, Handbook 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. Zbl0900.68316

## Citations in EuDML Documents

top## NotesEmbed ?

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