A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä

Avoiding square-free words on free groups




TekijätBadkobeh Golnaz, Harju Tero, Ochem Pascal, Rosenfeld Matthieu

KustantajaElsevier B.V.

Julkaisuvuosi2022

JournalTheoretical Computer Science

Tietokannassa oleva lehden nimiTheoretical Computer Science

Vuosikerta922

Aloitussivu206

Lopetussivu217

ISSN0304-3975

eISSN1879-2294

DOIhttps://doi.org/10.1016/j.tcs.2022.04.025

Verkko-osoitehttps://doi.org/10.1016/j.tcs.2022.04.025

Preprintin osoitehttp://arxiv.org/pdf/2104.06837


Tiivistelmä

We consider sets of factors that can be avoided in square-free words on two-generator free groups. The elements of the group are presented in terms of {0,1,2,3} such that 0 and 2 (resp., 1 and 3) are inverses of each other so that 02, 20, 13 and 31 do not occur in a reduced word. A Dean word is a reduced word that does not contain occurrences of uu for any nonempty u. Dean showed in 1965 that there exist infinite square-free reduced words. We show that if w is a Dean word of length at least 59 then there are at most six reduced words of length 3 avoided by w. We construct an infinite Dean word avoiding six reduced words of length 3. We also construct infinite Dean words with low critical exponent and avoiding fewer reduced words of length 3. Finally, we show that the minimal frequency of a letter in a Dean word is [Formula presented] and the growth rate is close to 1.45818. © 2022 Elsevier B.V.

Author keywords

Combinatorics on words; Square-free words



Last updated on 2024-26-11 at 22:54