Square-free words with one possible mismatch

N. V. Kotlyarov

Vestnik Moskovskogo universiteta. Matematika, mehanika, no. 1 (2016), pp. 48-52

Résumé

The paper is focused on some problems related to existence of periodic structures in words from formal languages. Squares, i.e. fragments of the form $xx$, where $x$ is some word, and squares with one error, i.e. fragments of the form $xy$, where the word $x$ is different from the word $y$ by only one letter, are considered. We study the existence of arbitrarily long words not containing squares with the length exceeding $l_0$ and squares with one error and the length more than $l_1$ depending on the natural numbers $l_0$, $l_1$. For all possible pairs $l_1\geq l_0$ we find the minimal alphabeth such that there exists an arbitrarily long word with these properties over this alphabeth.