RUS  ENG
Full version
JOURNALS // Vestnik Moskovskogo Universiteta. Seriya 1. Matematika. Mekhanika // Archive

Vestnik Moskov. Univ. Ser. 1. Mat. Mekh., 2016 Number 1, Pages 48–52 (Mi vmumm122)

This article is cited 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.

UDC: 519.765

Received: 17.10.2014


 English version:
Moscow University Mathematics Bulletin, Moscow University Mеchanics Bulletin, 2016, 71:1, 31–34

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024