Document Type
Article
Publication Date
10-5-2012
Journal
Theoretical Computer Science
Volume
454
First Page
38
Last Page
50
URL with Digital Object Identifier
10.1016/j.tcs.2012.04.001
Abstract
We investigate shuffle-decomposability into two words. We give an algorithm which takes as input a DFA M (under certain conditions) and determines the unique candidate decomposition into words u and v such that L(M) = u v ifM is shuffle decomposable, in time O(|u| + |v|). Even though this algorithm does not determine whether or not the DFA is shuffle decomposable, the sublinear time complexity of only determining the two words under the assumption of decomposability is surprising given the complexity of shuffle, and demonstrates an interesting property of the operation. We also show that for given words u and v and a DFA M we can determine whether u v ⊆ L(M) in polynomial time.
