Name
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)=uv if M 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 uv@?L(M) in polynomial time. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1016/j.tcs.2012.04.001 | Theor. Comput. Sci. |
Keywords | DocType | Volume |
DFA M,words u,unique candidate decomposition,time O,sublinear time complexity,polynomial time,certain condition,interesting property,shuffle decomposable,Algorithmic decomposition | Journal | 454, |
ISSN | Citations | PageRank |
0304-3975 | 3 | 0.45 |
References | Authors | |
4 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Franziska Biegler | 1 | 44 | 5.06 |
| Mark Daley | 2 | 166 | 22.18 |
| Ian McQuillan | 3 | 97 | 24.72 |