|
Vestnik Moskovskogo Universiteta. Seriya 1. Matematika. Mekhanika, 2016, Number 1, Pages 48–52
(Mi vmumm122)
|
|
|
|
This article is cited in 2 scientific papers (total in 2 papers)
Short notes
Square-free words with one possible mismatch
N. V. Kotlyarov Lomonosov Moscow State University, Faculty of Mechanics and Mathematics
Abstract:
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.
Key words:
Thue sequence, square-free words, word combinatorics, mismatches.
Received: 17.10.2014
Citation:
N. V. Kotlyarov, “Square-free words with one possible mismatch”, Vestnik Moskov. Univ. Ser. 1. Mat. Mekh., 2016, no. 1, 48–52; Moscow University Mathematics Bulletin, 71:1 (2016), 31–34
Linking options:
https://www.mathnet.ru/eng/vmumm122 https://www.mathnet.ru/eng/vmumm/y2016/i1/p48
|
|