Displaying similar documents to “On the topological complexity of infinitary rational relations”

Undecidability of topological and arithmetical properties of infinitary rational relations

Olivier Finkel (2003)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

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

Rational tree relations.

Raoult, Jean-Claude (1997)

Bulletin of the Belgian Mathematical Society - Simon Stevin

Similarity:

Iteration of rational transductions

Alain Terlutte, David Simplot (2000)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

On the continuity set of an Omega rational function

Olivier Carton, Olivier Finkel, Pierre Simonnet (2008)

RAIRO - Theoretical Informatics and Applications

Similarity:

In this paper, we study the continuity of rational functions realized by Büchi finite state transducers. It has been shown by Prieur that it can be decided whether such a function is continuous. We prove here that surprisingly, it cannot be decided whether such a function  has at least one point of continuity and that its continuity set cannot be computed. In the case of a synchronous rational function, we show that its continuity set is rational and that it can be computed....

Systolic tree acceptors

Karel Ii Culik, Arto Salomaa, Derick Wood (1984)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

A Hierarchy of Automatic -Words having a Decidable MSO Theory

Vince Bárány (2008)

RAIRO - Theoretical Informatics and Applications

Similarity:

We investigate automatic presentations of -words. Starting points of our study are the works of Rigo and Maes, Caucal, and Carton and Thomas concerning lexicographic presentation, MSO-interpretability in algebraic trees, and the decidability of the MSO theory of morphic words. Refining their techniques we observe that the lexicographic presentation of a (morphic) word is in a certain sense canonical. We then generalize our techniques to a hierarchy of classes of -words enjoying...