|
Vestnik Moskovskogo Universiteta. Seriya 1. Matematika. Mekhanika, 2018, Number 3, Pages 8–16
(Mi vmumm27)
|
|
|
|
Mathematics
Existence of words over a three-letter alphabet not containing squares with errors of replacing
N. V. Kotlyarov Yandex company, Moscow
Abstract:
The paper concerns some problems related to the existence of periodic structures in words from formal languages. Squares, i.e. fragments of the form $xx$, where $x$ is some word, and $\Delta$-squares, i.e. fragments of the form $xy$, where the word $x$ is different from the word $y$ by not more than $\Delta$ letters, are considered as periodic structures. We show the existence of arbitrarily long words over three-letter alphabet not containing $\Delta$-squares with the period exceeding $\Delta$. In particular, such words are constructed for all possible values $\Delta$.
Key words:
Thue sequence, square-free words, word combinatorics, mismatches.
Received: 13.09.2017
Citation:
N. V. Kotlyarov, “Existence of words over a three-letter alphabet not containing squares with errors of replacing”, Vestnik Moskov. Univ. Ser. 1. Mat. Mekh., 2018, no. 3, 8–16; Moscow University Mathematics Bulletin, 73:3 (2018), 90–97
Linking options:
https://www.mathnet.ru/eng/vmumm27 https://www.mathnet.ru/eng/vmumm/y2018/i3/p8
|
|