• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

Square-Free Words Obtained From Prefixes by Permutations

Tero Harju, Square-Free Words Obtained From Prefixes by Permutations. Theoretical Computer Science 429, 128–133, 2012.

http://dx.doi.org/10.1016/j.tcs.2011.12.031

Abstract:

An infinite square-free word w over a three letter alphabet T is said to have a k-stem σ if w=σw1w2⋯ where for each i, there exists a permutation πi of T which extended to a morphism gives wi=πi(σ). 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.

BibTeX entry:

@ARTICLE{jHarju_Tero12a,
  title = {Square-Free Words Obtained From Prefixes by Permutations},
  author = {Harju, Tero},
  journal = {Theoretical Computer Science},
  volume = {429},
  publisher = {Elsevier},
  pages = {128–133},
  year = {2012},
  keywords = {square free words, stem factorization, combinatorics on words},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Publication Forum rating of this publication: level 2

Edit publication