Computing the Rabin index of a parity automaton
Periodicity and roots of transfinite strings
This contribution extends the notions of roots and periodicity to strings of transfinite lengths. It shows that given a transfinite string, either it possesses a unique root or the set of its roots are equivalent in a strong way.
Periodicity and roots of transfinite strings
This contribution extends the notions of roots and periodicity to strings of transfinite lengths. It shows that given a transfinite string, either it possesses a unique root or the set of its roots are equivalent in a strong way.
Computing the Rabin Index of a Parity Automaton
The Rabin index of a rational language of infinite words given by a parity automaton with states is computable in time ( ) where is the cardinality of the alphabet. The number of values used by a parity acceptance condition is always greater than the Rabin index and conversely, the acceptance condition of a parity automaton can always be replaced by an equivalent acceptance condition whose number of used values is exactly the Rabin index. This new acceptance...
Computing the prefix of an automaton
Asynchronous sliding block maps
Decision problems among the main subfamilies of rational relations
We consider the four families of recognizable, synchronous, deterministic rational and rational subsets of a direct product of free monoids. They form a strict hierarchy and we investigate the following decision problem: given a relation in one of the families, does it belong to a smaller family? We settle the problem entirely when all monoids have a unique generator and fill some gaps in the general case. In particular, adapting a proof of Stearns, we show that it is recursively decidable whether...
Computing the prefix of an automaton
We present an algorithm for computing the prefix of an automaton. Automata considered are non-deterministic, labelled on words, and can have -transitions. The prefix automaton of an automaton has the following characteristic properties. It has the same graph as . Each accepting path has the same label as in . For each state , the longest common prefix of the labels of all paths going from to an initial or final state is empty. The interest of the computation of the prefix of an automaton...
Asynchronous sliding block maps
We define a notion of asynchronous sliding block map that can be realized by transducers labeled in * × *. We show that, under some conditions, it is possible to synchronize this transducer by state splitting, in order to get a transducer which defines the same sliding block map and which is labeled in × , where is a constant integer. In the case of a transducer with a strongly connected graph, the synchronization process can be considered as an implementation of an algorithm of Frougny...
Tree Automata and Automata on Linear Orderings
We show that the inclusion problem is decidable for rational languages of words indexed by scattered countable linear orderings. The method leans on a reduction to the decidability of the monadic second order theory of the infinite binary tree [9].
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...
An aperiodicity problem for multiwords
Multiwords are words in which a single symbol can be replaced by a nonempty set of symbols. They extend the notion of partial words. A word is in a multiword if it occurs in word that can be obtained by selecting one single symbol among the symbols provided in each position of . Motivated by a problem on incomplete databases, we investigate a variant of the pattern matching problem which is to decide whether a word is certain in a multiword . We study the language CERTAIN() of multiwords in which...
An aperiodicity problem for multiwords
Multiwords are words in which a single symbol can be replaced by a nonempty set of symbols. They extend the notion of partial words. A word is in a multiword if it occurs in word that can be obtained by selecting one single symbol among the symbols provided in each position of . Motivated by a problem on incomplete databases, we investigate a variant of the pattern matching problem which is to decide whether a word is certain in a multiword . We study the language CERTAIN() of multiwords in which...
Page 1