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

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},
     year = {2001},
     publisher = {EDP Sciences},
     volume = {35},
     number = {4},
     mrnumber = {1880806},
     zbl = {0994.68084},
     language = {en},
     url = {https://www.numdam.org/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  - https://www.numdam.org/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 https://www.numdam.org/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. https://www.numdam.org/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