Name
Abstract | ||
|---|---|---|
We investigate a special variant of the shuffle decomposition problem for regular languages; namely, when the given regular language is the shuffle of finite languages. The shuffle decomposition into finite languages is, in general, not unique. That is, there are L"1,L"2,L"3,L"4 with but {L"1,L"2}{L"3,L"4}. However, if all four languages are singletons (with at least two combined letters), it follows by a result of Berstel and Boasson [J. Berstel, L. Boasson, Shuffle factorization is unique, Theoretical Computer Science 273 (2002) 47-67] that the solution is unique; that is, {L"1,L"2}={L"3,L"4}. We further show that if L"1 and L"2 are arbitrary finite sets and L"3 and L"4 are singletons (with at least two letters in each), the solution is unique. Therefore, shuffle decomposition of words is unique not only over words, but over arbitrary sets. This is strong as we cannot let all four be arbitrary finite sets. Hopefully, the obtained results will help to better understand the very nature of the shuffle operation. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1016/j.tcs.2009.04.016 | Theor. Comput. Sci. |
Keywords | DocType | Volume |
shuffle decomposition problem,L. Boasson,Uniqueness,J. Berstel,finite language,shuffle operation,regular language,arbitrary set,arbitrary finite set,Words,shuffle factorization,Finite languages,shuffle decomposition,Shuffle decomposition | Journal | 410 |
Issue | ISSN | Citations |
38-40 | Theoretical Computer Science | 5 |
PageRank | References | Authors |
0.57 | 4 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Franziska Biegler | 1 | 44 | 5.06 |
| Mark Daley | 2 | 166 | 22.18 |
| Markus Holzer | 3 | 233 | 18.71 |
| Ian McQuillan | 4 | 97 | 24.72 |