Square-free shuffles of words

: Harju T, Muller M

: International Conference on WORDS

Publisher: ELSEVIER SCIENCE BV

: 2015

: Theoretical Computer Science

: THEORETICAL COMPUTER SCIENCE

: THEOR COMPUT SCI

: 601

: 29

: 38

: 10

: 0304-3975

DOI: https://doi.org/10.1016/j.tcs.2015.07.024(external)

Let u(sic)v denote the set of all shuffles of the words u and v. It is shown that for each integer n >= 3 there exists a square-free ternary word u of length n such that u(sic)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 is an element of u(sic)u. (C) 2015 Elsevier B.V. All rights reserved.