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/}
}
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