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/

[1] T. Araki and N. Tokura, Flow languages equal recursively enumerable languages. Acta Inform. 15 (1981) 209-217. | Zbl | MR

[2] D. Haussler and P. Zeiger, Very special languages and representations of recursively enumerable languages via computation stories. Inform. and Control 47 (1980) 201-212. | Zbl | MR

[3] J. Jȩdrzejowicz and A. Szepietowski, Shuffle languages are in P. Theoret. Comput. Sci. 250 (2001) 31-53. | Zbl | MR

[4] C. Martin-Vide and A. Mateescu, Special families of sewing languages, in Workshop - Descriptional complexity of automata, grammars and related structures. Magdeburg (1999) 137-143.

[5] C.H. Papadimitriou, Computational Complexity. Addison-Wesley Publ. Co (1994). | Zbl | MR

[6] A.C. Shaw, Software descriptions with flow expressions. IEEE Trans. Software Engrg. 3 (1978) 242-254. | Zbl

[7] K. Wagner and G. Wechsung, Computational Complexity. Reidel, Dordrecht, The Netherlands (1986). | Zbl | MR

[8] M.K. Warmuth and D. Haussler, On the complexity of iterated shuffle. J. Comput. Syst. Sci. 28 (1984) 345-358. | Zbl | MR