Hostname: page-component-7b7567c8c-7pwfn Total loading time: 0 Render date: 2026-11-17T16:04:45.171Z Has data issue: false hasContentIssue false

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
Affiliation:
Institute of Mathematics, University of Gdańsk, ul Wita Stwosza 57, 80952 Gdańsk, Poland; (jj@math.univ.gda.pl)
Andrzej Szepietowski
Affiliation:
Institute of Mathematics, University of Gdańsk, ul Wita Stwosza 57, 80952 Gdańsk, Poland; (matszp@math.univ.gda.pl)
Get access

Abstract

We investigate the complexity of languages described by some expressionscontaining shuffle operator and intersection. We show that deciding whetherthe 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, containsnon-semilinear languages and does not form a family of mildlycontext-sensitive languages.

Information

Type
Research Article
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.)

Article purchase

Temporarily unavailable