Square-Free Words with One Possible Mismatch / N. V. Kotlyarov. // Vestnik Moskovskogo Universiteta. Seriya 1. Matematika. Mekhanika. 2016. № 1. P. 48-52 [Moscow Univ. Math. Bulletin. Vol. 72, N 2, 2017. P. 31-34].

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\geq l_0 we find the minimal alphabet such that there exists an arbitrarily long word with these properties over this alphabet.

Key words: Thue sequence, square-free words, word combinatorics, mismatches.