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

Jȩdrzejowicz, Joanna, and Szepietowski, Andrzej. "On the expressive power of the shuffle operator matched with intersection by regular sets." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 35.4 (2001): 379-388. <http://eudml.org/doc/92672>.

@article{Jȩdrzejowicz2001,
abstract = {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 $L\cap R$, with a shuffle language $L$ and a regular language $R$, contains non-semilinear languages and does not form a family of mildly context- sensitive languages.},
author = {Jȩdrzejowicz, Joanna, Szepietowski, Andrzej},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {formal languages; shuffle; space complexity; complexity of languages},
language = {eng},
number = {4},
pages = {379-388},
publisher = {EDP-Sciences},
title = {On the expressive power of the shuffle operator matched with intersection by regular sets},
url = {http://eudml.org/doc/92672},
volume = {35},
year = {2001},
}

TY - JOUR
AU - Jȩdrzejowicz, Joanna
AU - Szepietowski, Andrzej
TI - On the expressive power of the shuffle operator matched with intersection by regular sets
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 2001
PB - EDP-Sciences
VL - 35
IS - 4
SP - 379
EP - 388
AB - 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 $L\cap R$, with a shuffle language $L$ and a regular language $R$, contains non-semilinear languages and does not form a family of mildly context- sensitive languages.
LA - eng
KW - formal languages; shuffle; space complexity; complexity of languages
UR - http://eudml.org/doc/92672
ER -