On the uniqueness of shuffle on words and finite languages

AbstractWe 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 L1,L2,L3,L4 with but {L1,L2}≠{L3,L4}. 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, {L1,L2}={L3,L4}. We further show that if L1 and L2 are arbitrary finite sets and L3 and L4 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