Square-free words obtained from prefixes by permutations
: Harju T
Publisher: ELSEVIER SCIENCE BV
: 2012
: Theoretical Computer Science
: THEORETICAL COMPUTER SCIENCE
: THEOR COMPUT SCI
: 429
: 128
: 133
: 6
: 0304-3975
DOI: https://doi.org/10.1016/j.tcs.2011.12.031
: https://research.utu.fi/converis/portal/detail/Publication/1867478
An infinite square-free word w over a three letter alphabet T is said to have a k-stem sigma if w = sigma w(1)w(2) ... where for each i, there exists a permutation pi(i) of T which extended to a morphism gives w(i) = pi(i)(sigma). We show that there exists an infinite k-stem word for k = 1, 2, 3, 9 and 13 <= k <= 19, but not for 4 <= k <= 8 and 10 <= k <= 12. The problem whether k-stem words exist for each k >= 20 remains open. (C) 2011 Elsevier B.V. All rights reserved.
UTU Research Portal