Infinite self-shuffling words

DOI10.1016/J.JCTA.2014.07.008zbMATH Open1309.68161OpenAlexW2050080033MaRDI QIDQ458277FDOQ458277

Authors Émilie Charlier, Teturo Kamae, Svetlana Puzynina, Luca Q. Zamboni

Publication date 7 October 2014

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1302.3844

zbMATH Keywords

Lyndon wordsThue-Morse wordSturmian wordsmorphic wordsword shuffling

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Abstract: In this paper we introduce and study a new property of infinite words: An infinite word $xin{A}^{m}athbbN$, with values in a finite set $A$, is said to be $k$-self-shuffling $(kgeq2)$ if $x$ admits factorizations: $x=pro{d}_{i=0}^{i}nfty{U}_i^{(1)}cdots{U}_i^{(k)}=pro{d}_{i=0}^{i}nfty{U}_i^{(1)}=cdots=pro{d}_{i=0}^{i}nfty{U}_i^{(k)}$. In other words, there exists a shuffle of $k$-copies of $x$ which produces $x$. We are particularly interested in the case $k=2$, in which case we say $x$ is self-shuffling. This property of infinite words is shown to be an intrinsic property of the word and not of its language (set of factors). For instance, every aperiodic word contains a non self-shuffling word in its shift orbit closure. While the property of being self-shuffling is a relatively strong condition, many important words arising in the area of symbolic dynamics are verified to be self-shuffling. They include for instance the Thue-Morse word and all Sturmian words of intercept $0<ho<1$ (while those of intercept $ho=0$ are not self-shuffling). Our characterization of self-shuffling Sturmian words can be interpreted arithmetically in terms of a dynamical embedding and defines an arithmetic process we call the {it stepping stone model}. One important feature of self-shuffling words stems from its morphic invariance, which provides a useful tool for showing that one word is not the morphic image of another. The notion of self-shuffling has other unexpected applications particularly in the area of substitutive dynamical systems. For example, 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.

Recommendations

• Self-shuffling words
• On shuffling of infinite square-free words
• Square-free words with square-free self-shuffles
• Square-free shuffles of words
• A note on square-free shuffles of words

Cites work

• scientific article; zbMATH DE number 1740032 (Why is no real title available?)
• scientific article; zbMATH DE number 1737190 (Why is no real title available?)
• A characterization of substitutive sequences using return words
• A generalization of Sturmian sequences: Combinatorial structure and transcendence
• A little more about morphic Sturmian words
• Automatic Sequences
• Infinite Lyndon words
• MINIMAL DUVAL EXTENSIONS
• On Sturmian sequences which are invariant under some substitutions
• On recognizing words that are squares for the shuffle product
• On substitution invariant Sturmian words: an application of Rauzy fractals
• Results and trends in theoretical computer science, Colloquium in honor of Arto Salomaa, Graz, Austria, June 10-11, 1994. Proceedings
• Self-shuffling words
• Shuffling and unshuffling
• Sturmian words: structure, combinatorics, and their arithmetics
• Toeplitz words, generalized periodicity and periodically iterated morphisms
• Unshuffling a square is NP-hard

Cited in

(12)

• The least self-shuffle of the Thue-Morse sequence
• A characterization of binary morphisms generating Lyndon infinite words
• On shuffling of infinite square-free words
• Infinite Wordle and the mastermind numbers
• Intertwined infinite binary words
• Infinite words containing squares at every position
• Aperiodic pseudorandom number generators based on infinite words
• Abelian combinatorics on words: a survey
• Self-shuffling words
• Expansions of generalized Thue-Morse numbers
• Abelian bordered factors and periodicity
• Self-similar measures and sequences

This page was built for publication: Infinite self-shuffling words

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q458277)