Abstract
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\in \mathbb{A}^{\mathbb N},\) defined over a finite alphabet \(\mathbb{A}\), is 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 \mathbb{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.
The first and fourth authors are supported in part by FiDiPro grant of the Academy of Finland. The third author is supported in part by the Academy of Finland under grant 251371, by Russian Foundation of Basic Research (grant 12-01-00448), and by RF President grant MK-4075.2012.1. Preliminary version: http://arxiv.org/abs/1302.3844.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Allouche, J.-P., Shallit, J.: The ubiquitous Prouhet-Thue-Morse sequence. In: Ding, C., Helleseth, T., Niederreiter, H. (eds.) Proceedings of Sequences and Their Applications, SETA 1998, pp. 1–16. Springer (1999)
Allouche, J.-P., Shallit, J.: Automatic sequences. In: Theory, Applications, Generalizations. Cambridge University Press (2003)
Berthé, V., Ei, H., Ito, S., Rao, H.: On substitution invariant Sturmian words: an application of Rauzy fractals. Theor. Inform. Appl. 41, 329–349 (2007)
Cassaigne, J., Karhumäki, J.: Toeplitz Words, Generalized Periodicity and Periodically Iterated Morphisms. European J. Combin. 18, 497–510 (1997)
Henshall, D., Rampersad, N., Shallit, J.: Shuffling and unshuffling. Bull. EATCS 107, 131–142 (2012)
Fagnot, I.: A little more about morphic Sturmian words. Theor. Inform. Appl. 40, 511–518 (2006)
Lothaire, M.: Algebraic Combinatorics on Words. Encyclopedia of Mathematics and its Applications, vol. 90. Cambridge University Press, U.K (2002)
Morse, M., Hedlund, G.A.: Symbolic dynamics II: Sturmian sequences. Amer. J. Math. 62, 1–42 (1940)
Thue, A.: Über unendliche Zeichenreihen. Norske Vid. Selsk. Skr. I Math-Nat. Kl. 7, 1–22 (1906)
Yasutomi, S.-I.: On sturmian sequences which are invariant under some substitutions. In: Kanemitsu, S., et al. (eds.) Number Theory and Its Applications, Proceedings of the Conference held at the RIMS, Kyoto, Japan, November 10-14, 1997, pp. 347–373. Kluwer Acad. Publ., Dordrecht (1999)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Charlier, É., Kamae, T., Puzynina, S., Zamboni, L.Q. (2013). Self-shuffling Words. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds) Automata, Languages, and Programming. ICALP 2013. Lecture Notes in Computer Science, vol 7966. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-39212-2_13
Download citation
DOI: https://doi.org/10.1007/978-3-642-39212-2_13
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-39211-5
Online ISBN: 978-3-642-39212-2
eBook Packages: Computer ScienceComputer Science (R0)