Infinite square-free self-shuffling words

2014/01/25 by Mike Müller, Müller, Mike, Svetlana Puzynina +3
Computer Science · Mathematics · Psychology · #Cellular Automata and Applications #Phonetics and Phonology Research #cs.DM #cs.FL #math.CO #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1401.6536

arxiv created 2014/11/08 · arxiv updated 2014/11/11

Abstract

In this paper we answer two recent questions from Charlier et al. and Harju about self-shuffling words. An infinite word w is called self-shuffling, if w=∏_i=0^∞ U_iV_i=∏_i=0^∞ U_i=∏_i=0^∞ V_i for some finite words U_i, V_i. Harju recently asked whether square-free self-shuffling words exist. We answer this question affirmatively. Besides that, we build an infinite word such that no word in its shift orbit closure is self-shuffling, answering positively a question from Charlier et al.

Related

• Square-Free Shuffles of Words
• On the Self Shuffle Language
• The Frobenius problem for the shuffle operation
• Shuffling and Unshuffling
• Variations on shuffle squares