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.
last update: 27.9.2007, webmaster: Petr Ambrož