Geodesic
On the expressive power of the shuffle operator matched with intersection by regular sets
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 35 (2001) no. 4, pp. 379-388

Voir la notice de l'article provenant de la source Numdam

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

Classification : 68Q15, 68Q45
Keywords: formal languages, shuffle, space complexity 
@article{ITA_2001__35_4_379_0,
     author = {J\c{e}drzejowicz, Joanna and Szepietowski, Andrzej},
     title = {On the expressive power of the shuffle operator matched with intersection by regular sets},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {379--388},
     publisher = {EDP-Sciences},
     volume = {35},
     number = {4},
     year = {2001},
     mrnumber = {1880806},
     zbl = {0994.68084},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/ITA_2001__35_4_379_0/}
}
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
SP  - 379
EP  - 388
VL  - 35
IS  - 4
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/item/ITA_2001__35_4_379_0/
LA  - en
ID  - ITA_2001__35_4_379_0
ER  - 
%0 Journal Article
%A Jȩdrzejowicz, Joanna
%A Szepietowski, Andrzej
%T On the expressive power of the shuffle operator matched with intersection by regular sets
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2001
%P 379-388
%V 35
%N 4
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/item/ITA_2001__35_4_379_0/
%G en
%F ITA_2001__35_4_379_0
Jȩdrzejowicz, Joanna; 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, Tome 35 (2001) no. 4, pp. 379-388. http://geodesic.mathdoc.fr/item/ITA_2001__35_4_379_0/