Avoiding square-free words on free groups

Badkobeh, Golnaz; Harju, Tero; Ochem, Pascal and Rosenfeld, Matthieu. 2022. Avoiding square-free words on free groups. Theoretical Computer Science, ISSN 0304-3975 [Article]

No full text available
[img] Text
Dean(1).pdf - Accepted Version
Permissions: Administrator Access Only until 26 April 2023.
Available under License Creative Commons Attribution Non-commercial No Derivatives.

Download (261kB)

Abstract or Description

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 8 and the growth rate is close to 1.45818.

Item Type:

Article

Identification Number (DOI):

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

Keywords:

Combinatorics on words, Square-free words

Departments, Centres and Research Units:

Computing

Dates:

DateEvent
21 April 2022Accepted
8 June 2022Published Online
24 June 2022Published

Item ID:

31913

Date Deposited:

15 Jun 2022 08:54

Last Modified:

20 Jun 2022 08:36

Peer Reviewed:

Yes, this version has been peer-reviewed.

URI:

https://research.gold.ac.uk/id/eprint/31913

View statistics for this item...

Edit Record Edit Record (login required)