2021/05/10 by Antoine Domenech, Pascal Ochem, Domenech, Antoine +1
Arts and Humanities · Computer Science · #Combinatorics (math.CO) #FOS: Mathematics #Language, Linguistics, Cultural Analysis #Natural Language Processing Techniques #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2105.04673
openalex publication_date 2021/05/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In combinatorics on words, a word w over an alphabet Σ is said to avoid a pattern p over an alphabet Δ if there is no factor f of w such that f=h(p) where h:Δ^*→Σ^* is a non-erasing morphism. A pattern p is said to be k-avoidable if there exists an infinite word over a k-letter alphabet that avoids p. A pattern is doubled if every variable occurs at least twice. Doubled patterns are known to be 3-avoidable. Currie, Mol, and Rampersad have considered a generalized notion which allows variable occurrences to be reversed. That is, h(VR) is the mirror image of h(V) for every V∈Δ. We show that doubled patterns with reversal are 3-avoidable. We also conjecture that (classical) doubled patterns that do not contain a square are 2-avoidable. We confirm this conjecture for patterns with at most 4 variables. This implies that for every doubled pattern p, the growth rate of ternary words avoiding p is at least the growth rate of ternary square-free words. A previous version of this paper containing only the first result has been presented at WORDS 2021.