Square-Free Shuffles of Words
Preprint
Abstract
Let $u \shuffle v$ denote the set of all shuffles of the words $u$ and $v$. It is shown that for each integer $n \geq 3$ there exists a square-free ternary word $u$ of length $n$ such that $u\shuffle u$ contains a square-free word. This property is then shown to also hold for infinite words, i.e., there exists an infinite square-free word $u$ on three letters such that $u$ can be shuffled with itself to produce an infinite square-free word $w \in u \shuffle u$.
Keywords
All Related Versions
This publication has 8 references indexed in Scilit:
- Unshuffling a square is NP-hardJournal of Computer and System Sciences, 2014
- Infinite ternary square-free words concatenated from permutations of a single wordTheoretical Computer Science, 2013
- Square-free words obtained from prefixes by permutationsTheoretical Computer Science, 2012
- Cubefree words with many squaresDiscrete Mathematics & Theoretical Computer Science, 2010
- Avoiding large squares in infinite binary wordsTheoretical Computer Science, 2005
- Uniformly growing k-th power-free homomorphismsTheoretical Computer Science, 1988
- Sharp characterizations of squarefree morphismsTheoretical Computer Science, 1982
- Avoidable patterns in strings of symbolsPacific Journal of Mathematics, 1979