Some Variations on a Theme of Irina Mel'nichuk Concerning the Avoidability of Patterns in Strings of Symbols

George F. McNulty

Abstract


The set of all doubled patterns on $n$ or fewer letters can be avoided on an alphabet with $k$ letters, where $k$ is the least even integer strictly greater than $n+1$, with the exception of $n=4$. The set of all doubled patterns on $4$ or fewer letters can be avoided on the $8$-letter alphabet. The set of all avoidable patterns on $n$ or fewer letters can be avoided on an alphabet with $2(n+2)$ letters.


Keywords


Avoidable words; Doubled words; Global avoidability

Full Text:

PDF