
In combinatorics on words, a word $w$ over an alphabet $\Sigma$ is said to avoid a pattern $p$ over an alphabet $\Delta$ if there is no factor $x$ of $w$ and no non-erasing morphism $h$ from $\Delta^*$ to $\Sigma^*$ such that $h(p) = x$. Bell and Goh have recently applied an algebraic technique due to Golod to show that for a certain wide class of patterns $p$ there are exponentially many words of length $n$ over a $4$-letter alphabet that avoid $p$. We consider some further consequences of their work. In particular, we show that any pattern with $k$ variables of length at least $4^k$ is avoidable on the binary alphabet. This improves an earlier bound due to Cassaigne and Roth.
FOS: Computer and information sciences, Combinatorics on words, Formal Languages and Automata Theory (cs.FL), FOS: Mathematics, Mathematics - Combinatorics, Computer Science - Formal Languages and Automata Theory, Combinatorics (math.CO), 68R15, binary alphabet
FOS: Computer and information sciences, Combinatorics on words, Formal Languages and Automata Theory (cs.FL), FOS: Mathematics, Mathematics - Combinatorics, Computer Science - Formal Languages and Automata Theory, Combinatorics (math.CO), 68R15, binary alphabet
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 6 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
