RAIRO - Theoretical Informatics and Applications (RAIRO: ITA)

Issue		Theoret. Informatics Appl. Volume 35, Number 4, July-August 2001
Page(s)		379 - 388
DOI		10.1051/ita:2001125

DOI: 10.1051/ita:2001125

Theoret. Informatics Appl. 35, 379-388 (2001)

On the expressive power of the shuffle operator matched with intersection by regular sets

Joanna Jedrzejowicz and Andrzej Szepietowski

Institute of Mathematics, University of Gdansk, ul Wita Stwosza 57, 80952 Gdansk, Poland; (jj@math.univ.gda.pl matszp@math.univ.gda.pl)

(Received December, 2000. Accepted October, 2001)

Abstract
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\cap 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.

What is OpenURL?