Algorithmic decomposition of shuffle on words

作者：Biegler Franziska; Daley Mark^*; McQuillan Ian

来源：Theoretical Computer Science, 2012, 454: 38-50.

DOI：10.1016/j.tcs.2012.04.001

• Shuffle decomposition
• Finite languages
• Finite automata
• Words

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 (sic) v if M is shuffle decomposable, in time O(vertical bar u vertical bar + vertical bar v vertical bar). 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. %26lt;br%26gt;We also show that for given words u and u and a DFA M we can determine whether u (sic) v subset of L(M) in polynomial time.

• 出版日期2012-10-5