On the topological complexity of infinitary rational relations
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].
Undecidability of topological and arithmetical properties of infinitary rational relations
We prove that for every countable ordinal one cannot decide whether a given infinitary rational relation is in the Borel class (respectively ). Furthermore one cannot decide whether a given infinitary rational relation is a Borel set or a -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...
Some problems in automata theory which depend on the models of set theory
We prove that some fairly basic questions on automata reading infinite words depend on the models of the axiomatic system ZFC. It is known that there are only three possibilities for the cardinality of the complement of an -language (x1d49c;) accepted by a Büchi 1-counter automaton x1d49c;. We prove the following surprising result: there exists a 1-counter Büchi automaton x1d49c; such that the cardinality of the complement (𝒜) of the -language ...
Undecidability of Topological and Arithmetical Properties of Infinitary Rational Relations
We prove that for every countable ordinal one cannot decide whether a given infinitary rational relation is in the Borel class (respectively ). Furthermore one cannot decide whether a given infinitary rational relation is a Borel set or a -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...
On the Topological Complexity of Infinitary Rational Relations
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].
Highly Undecidable Problems For Infinite Computations
We show that many classical decision problems about -counter -languages, context free -languages, or infinitary rational relations, are Π½ -complete, hence located at the second level of the analytical hierarchy, and “highly undecidable”. In particular, the universality problem, the inclusion problem, the equivalence problem, the determinizability problem, the complementability problem, and the unambiguity problem are all Π½ -complete for context-free -languages or for infinitary rational relations....
Some problems in automata theory which depend on the models of set theory
We prove that some fairly basic questions on automata reading infinite words depend on the models of the axiomatic system
The isomorphism relation between tree-automatic Structures
An ω-tree-automatic structure is a relational structure whose domain and relations are accepted by Muller or Rabin tree automata. We investigate in this paper the isomorphism problem for ω-tree-automatic structures. We prove first that the isomorphism relation for ω-tree-automatic boolean algebras (respectively, partial orders, rings, commutative rings, non commutative rings, non commutative groups, nilpotent groups of class n ≥ 2) is not determined by the axiomatic system ZFC. Then we prove that...
On the continuity set of an Omega rational function
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. Furthermore...
Page 1