A1 Refereed original research article in a scientific journal
Square-free words obtained from prefixes by permutations
Authors: Harju T
Publisher: ELSEVIER SCIENCE BV
Publication year: 2012
Journal: Theoretical Computer Science
Journal name in source: THEORETICAL COMPUTER SCIENCE
Journal acronym: THEOR COMPUT SCI
Volume: 429
First page : 128
Last page: 133
Number of pages: 6
ISSN: 0304-3975
DOI: https://doi.org/10.1016/j.tcs.2011.12.031
Self-archived copy’s web address: https://research.utu.fi/converis/portal/detail/Publication/1867478
Abstract
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.
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.
Downloadable publication This is an electronic reprint of the original article. |  |
UTU Research Portal