Square-free words with one possible mismatch
Nikita Vladimirovich Kotlyarov · Moscow University Mathematics Bulletin · 2016
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 in 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 > l 0 we find the minimal alphabet such that there exists an arbitrarily long word with these properties over this alphabet.