Shuffle quotient and decompositions
|Title||Shuffle quotient and decompositions|
|Author(s)||Cezar Campeanu, K. Salomaa, S. Vagvolgyi|
|Journal||Lecture Notes in Computer Science, Developments in Language Theory|
|Abstract||We introduce a right congruence relation that is the analogy of the Nerode congruence when catenation is replaced by shuffle. Using this relation we show that for certain subclasses of regular languages the shuffle decomposition problem is decidable. We show that shuffle decomposition is undecidable for context-free languages.|
Using APA 6th Edition citation style.
Times viewed: 145