On the Self Shuffle Language
This work addresses a theoretical problem in formal language theory, specifically for researchers studying shuffle operations and language classification, and is incremental as it builds on prior research on the shuffle product.
The paper investigates the self shuffle (shuffle square) of words, showing that the self shuffle language differs from the shuffle of the language, proving it is context sensitive but not context free, and demonstrating that the self shuffle uniquely determines the original word.
The shuffle product \(u\shuffle v\) of two words \(u\) and \(v\) is the set of all words which can be obtained by interleaving \(u\) and \(v\). Motivated by the paper \emph{The Shuffle Product: New Research Directions} by Restivo (2015) we investigate a special case of the shuffle product. In this work we consider the shuffle of a word with itself called the \emph{self shuffle} or \emph{shuffle square}, showing first that the self shuffle language and the shuffle of the language are in general different sets. We prove that the language of all words arising as a self shuffle of some word is context sensitive but not context free. Furthermore, we show that the self shuffle \(w \shuffle w\) uniquely determines \(w\).