Combinatorical and Algebraic Structures Seminar

Session details

Date: 6.5.2014
Speaker: Svetlana Puzynina, Sobolev Institute of Mathematics \& University of Turku
Title: Infinite self-shuffling words
Abstract: (spoluautoři: E. Charlier, T. Kamae, M. Muller, M. Rao, and L.Q. Zamboni)
In this talk we introduce and study a new property of infinite words: An infinite word $x$ on an alphabet $A$ is said to be it self-shuffling, if $x$ admits factorizations: $x=\prod_{i=1}^\infty U_iV_i=\prod_{i=1}^\infty U_i=\prod_{i=1}^\infty V_i$ with $U_i,V_i \in A^*$. In other words, there exists a shuffle of $x$ with itself which reproduces $x$. We prove that many important and well studied words are self-shuffling: This includes the Thue-Morse word and all Sturmian words (except those of the form $aC$ where $a\in\{0,1\}$ and $C$ is a characteristic Sturmian word). We further establish a number of necessary conditions for a word to be self-shuffling, and show that certain other important words (including the paper-folding word and infinite Lyndon words) are not self-shuffling. One important feature of self-shuffling words is its morphic invariance: The morphic image of a self-shuffling word is again self-shuffling. This provides a useful tool for showing that one word is not the morphic image of another. In addition to its morphic invariance, this new notion has other unexpected applications: For instance, as a consequence of our characterization of self-shuffling Sturmian words, we recover a number theoretic result, originally due to Yasutomi, on a classification of pure morphic Sturmian words in the orbit of the characteristic. Finally, we provide an example of a square-free self-shuffling word, answering the question of T.~Harju.

Return to index.