Loading [MathJax]/extensions/MathZoom.js
Topological and Arithmetical Properties of Infinitary Rational Relations
Finkel, Olivier
HAL, hal-00114323 / Harvested from HAL
We study the topological complexity of infinitary rational relations, with regard to the Borel and projective hierarchies. In particular we show that there exists some infinitary rational relations which are analytic but non Borel sets hence also non arithmetical sets, giving an answer to a question of Simonnet [Automates et théorie descriptive, Ph. D. Thesis, Université Paris 7, March 1992]. We then deduce the undecidability of numerous topological and arithmetical properties of infinitary rational relations.
Publié le : 2002-07-05
Classification:  [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO],  [MATH.MATH-LO]Mathematics [math]/Logic [math.LO]
@article{hal-00114323,
     author = {Finkel, Olivier},
     title = {Topological and Arithmetical Properties of Infinitary Rational Relations},
     journal = {HAL},
     volume = {2002},
     number = {0},
     year = {2002},
     language = {en},
     url = {http://dml.mathdoc.fr/item/hal-00114323}
}
Finkel, Olivier. Topological and Arithmetical Properties of Infinitary Rational Relations. HAL, Tome 2002 (2002) no. 0, . http://gdmltest.u-ga.fr/item/hal-00114323/