Displaying similar documents to “Undecidability of topological and arithmetical properties of infinitary rational relations”

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

On the topological complexity of infinitary rational relations

Olivier Finkel (2003)

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

Similarity:

We prove in this paper that there exists some infinitary rational relations which are analytic but non Borel sets, giving an answer to a question of Simonnet [20].

Iteration of rational transductions

Alain Terlutte, David Simplot (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

The purpose of this paper is to show connections between iterated length-preserving rational transductions and linear space computations. Hence, we study the smallest family of transductions containing length-preserving rational transductions and closed under union, composition and iteration. We give several characterizations of this class using restricted classes of length-preserving rational transductions, by showing the connections with "context-sensitive transductions" and transductions...

Iteration of rational transductions

Alain Terlutte, David Simplot (2000)

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

Similarity:

Closure under union and composition of iterated rational transductions

D. Simplot, A. Terlutte (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

We proceed our work on iterated transductions by studying the closure under union and composition of some classes of iterated functions. We analyze this closure for the classes of length-preserving rational functions, length-preserving subsequential functions and length-preserving sequential functions with terminal states. All the classes we obtain are equal. We also study the connection with deterministic context-sensitive languages.