A shuffle ideal is a language which is a finite union of languages of the form where is a finite alphabet and the ’s are letters. We show how to represent shuffle ideals by special automata and how to compute these representations. We also give a temporal logic characterization of shuffle ideals and we study its expressive power over infinite words. We characterize the complexity of deciding whether a language is a shuffle ideal and we give a new quadratic algorithm for this problem. Finally...
A shuffle ideal is a language which is a finite union of
languages of the form where is a
finite alphabet and the
's are letters. We show how to represent
shuffle ideals by special automata and how to compute these
representations. We also give a temporal logic characterization of
shuffle ideals and we study its expressive power over infinite words.
We characterize the complexity of deciding whether a language is a
shuffle ideal and we give a new quadratic algorithm for...
A reversible automaton is a finite automaton in which each
letter induces a partial one-to-one map from the set of states into
itself. We solve the following problem proposed by Pin. Given an
alphabet , does there exist a sequence of languages
on
which can be accepted by a reversible automaton, and such that the
number of states of the minimal automaton of
is in (), while
the minimal number of states of a reversible automaton accepting
...
Computing the image of a regular language by the transitive closure of a relation is a central question in regular model checking. In a recent paper Bouajjani et al. [IEEE Comput. Soc. (2001) 399–408] proved that the class of regular languages – called APC – of the form
, where the union is finite and each is either a single symbol or a language of the form with a subset of the alphabet, is closed under...
Computing the image of a regular language by the transitive closure of a
relation is a central question in regular model checking. In a recent
paper Bouajjani [ (2001) 399–408] proved that the class of
regular languages – called APC – of the form U
..., where the union is finite and each
is either a single symbol or a language of the form with
a subset of the alphabet, is closed under all semi-commutation
relations . Moreover a recursive...
Download Results (CSV)