Shuffle decompositions of regular languages
|Title||Shuffle decompositions of regular languages|
|Author(s)||Cezar Campeanu, K. Salomaa, S. Vagvolgyi|
|Journal||International Journal of Foundations of Computer Science|
|Abstract||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.|
Using APA 6th Edition citation style.
Times viewed: 267