Self-shuffling Words

摘要

In this paper we introduce and study a new property of infinite words which is invariant under the action of a morphism: We say an infinite word x ∈ A~N, defined over a finite alphabet A, is self-shuffling if x admits factorizations: x =∏_(i=1)~∞U_iV_i =∏_(i=1)~∞U_i =∏_(i=1)~∞ V_i with U_i,V_i ∈ A~+. In other words, there exists a shuffle of x with itself which reproduces x. The morphic image of any self-shuffling word is again self-shuffling. 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 ∈ {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. In addition to its morphic invariance, which can be used to show that one word is not the morphic image of another, 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, which characterizes pure morphic Sturmian words in the orbit of the characteristic.