On the expressive power of the shuffle operator matched with intersection by regular sets
Institute of Mathematics, University of Gdańsk,
ul Wita Stwosza 57, 80952 Gdańsk, Poland; (firstname.lastname@example.org)
2 Institute of Mathematics, University of Gdańsk, ul Wita Stwosza 57, 80952 Gdańsk, Poland; (email@example.com)
Accepted: October 2001
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 , 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.
Mathematics Subject Classification: 68Q15 / 68Q45
Key words: Formal languages / shuffle / space complexity.
© EDP Sciences, 2001