Hostname: page-component-cd9895bd7-8ctnn Total loading time: 0 Render date: 2024-12-27T08:56:27.380Z Has data issue: false hasContentIssue false
  • English
  • Français

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

Published online by Cambridge University Press:  15 April 2002

Joanna Jędrzejowicz  and
Andrzej Szepietowski
Joanna Jędrzejowicz
Affiliation:
Institute of Mathematics, University of Gdańsk, ul Wita Stwosza 57, 80952 Gdańsk, Poland; ([email protected])
Andrzej Szepietowski
Affiliation:
Institute of Mathematics, University of Gdańsk, ul Wita Stwosza 57, 80952 Gdańsk, Poland; ([email protected])
Get access

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.

Keywords

Formal languagesshufflespace complexity.
Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 35 , Issue 4 , July 2001 , pp. 379 - 388
Copyright
© EDP Sciences, 2001

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Araki, T. and Tokura, N., Flow languages equal recursively enumerable languages. Acta Inform. 15 (1981) 209-217. CrossRef
Haussler, D. and Zeiger, P., Very special languages and representations of recursively enumerable languages via computation stories. Inform. and Control 47 (1980) 201-212. CrossRef
Jedrzejowicz, J. and Szepietowski, A., Shuffle languages are in P. Theoret. Comput. Sci. 250 (2001) 31-53. CrossRef
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.
C.H. Papadimitriou, Computational Complexity. Addison-Wesley Publ. Co (1994).
Shaw, A.C., Software descriptions with flow expressions. IEEE Trans. Software Engrg. 3 (1978) 242-254. CrossRef
K. Wagner and G. Wechsung, Computational Complexity. Reidel, Dordrecht, The Netherlands (1986).
Warmuth, M.K. and Haussler, D., On the complexity of iterated shuffle. J. Comput. Syst. Sci. 28 (1984) 345-358. CrossRef