On the expressive power of the shuffle operator matched with intersection by regular sets
Jȩdrzejowicz, Joanna ; Szepietowski, Andrzej
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 35 (2001), p. 379-388 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

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.

Publié le : 2001-01-01
Classification:  68Q15,  68Q45 
@article{ITA_2001__35_4_379_0,
     author = {J\c edrzejowicz, 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},
     volume = {35},
     year = {2001},
     pages = {379-388},
     mrnumber = {1880806},
     zbl = {0994.68084},
     language = {en},
     url = {http://dml.mathdoc.fr/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) pp. 379-388. http://gdmltest.u-ga.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. | 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