SHUFFLE DECOMPOSITIONS OF REGULAR LANGUAGES
Cezar Câmpeanu, Kai Salomaa, Sándor Vágvölgyi · International Journal of Foundations of Computer Science · 2002
We study the shuffle quotient operation and introduce equivalence relations it defines with respect to a (regular) language. Corresponding to an arbitrary shuffle decomposition we construct a normalized decomposition that is defined in terms of maximal languages. Using closure properties of the normalized decompositions we show that for certain subclasses of regular languages we can effectively decide whether or not the language has a non-trivial shuffle decomposition. We show that shuffle decomposition is undecidable for context-free languages.