Displaying similar documents to “The helping hierarchy”

On the expressive power of the shuffle operator matched with intersection by regular sets

Joanna Jȩdrzejowicz, Andrzej Szepietowski (2001)

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

Similarity:

We investigate the complexity of languages described by some expressions containing shuffle operator and intersection. We show that deciding whether the shuffle of two words has a nonempty intersection with a regular set (or fulfills some regular pattern) is NL-complete. Furthermore we show that the class of languages of the form , with a shuffle language and a regular language , contains non-semilinear languages and does not form a family of mildly context- sensitive languages. ...

Equality sets for recursively enumerable languages

Vesa Halava, Tero Harju, Hendrik Jan Hoogeboom, Michel Latteux (2005)

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

Similarity:

We consider shifted equality sets of the form , where and are nonerasing morphisms and is a letter. We are interested in the family consisting of the languages , where is a coding and is a shifted equality set. We prove several closure properties for this family. Moreover, we show that every recursively enumerable language is a projection of a shifted equality set, that is, for some (nonerasing) morphisms and and a letter , where deletes the letters not in . Then...

Self-reproducing pushdown transducers

Alexander Meduna, Luboš Lorenc (2005)

Kybernetika

Similarity:

After a translation of an input string, , to an output string, , a self- reproducing pushdown transducer can make a self-reproducing step during which it moves to its input tape and translates it again. In this self- reproducing way, it can repeat the translation -times for any . This paper demonstrates that every recursively enumerable language can be characterized by the domain of the translation obtained from a self- reproducing pushdown transducer that repeats its translation...

Efficiency of automata in semi-commutation verification techniques

Gérard Cécé, Pierre-Cyrille Héam, Yann Mainier (2008)

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

Similarity:

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