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 LR, 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
Mots clés : 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},
     zbl = {0994.68084},
     mrnumber = {1880806},
     language = {en},
     url = {http://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
DA  - 2001///
SP  - 379
EP  - 388
VL  - 35
IS  - 4
PB  - EDP-Sciences
UR  - http://www.numdam.org/item/ITA_2001__35_4_379_0/
UR  - https://zbmath.org/?q=an%3A0994.68084
UR  - https://www.ams.org/mathscinet-getitem?mr=1880806
LA  - en
ID  - ITA_2001__35_4_379_0
ER  - 
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://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. | MR 625161 | Zbl 0456.68093

[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. | MR 617490 | Zbl 0457.68086

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

[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). | MR 1251285 | Zbl 0833.68049

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

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

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