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
Date 2002
Volume 13
Issue 6
Start page 799
End page 816
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.
DOI 10.1142/S0129054102001461

Using APA 6th Edition citation style.

[Page generation failure. The bibliography processor requires a browser with Javascript enabled.]

Times viewed: 480

Adding this citation to "My List" will allow you to export this citation in other styles.