On the Self Shuffle Language

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$.

No reviews yet.

No comments yet.