|
Existence of words over a binary alphabet free from squares with mismatches
N. V. Kotlyarov Yandex
Abstract:
The paper is concerned with the problem of existence of periodic structures in words from formal languages. Squares (that is, fragments of the form $xx$, where $x$ is an arbitrary word) and $\Delta$-squares (that is, fragments of the form $xy$, where a word $x$ differs from a word $y$ by at most $\Delta$ letters) are considered as periodic structures. We show that in a binary alphabet there exist arbitrarily long words free from $\Delta$-squares with length at most $4\Delta+4$. In particular, a method of construction of such words for any $\Delta$ is given.
Keywords:
Thue sequence, square-free words, word combinatorics, mismatches.
Received: 28.09.2017 Revised: 20.02.2018
Citation:
N. V. Kotlyarov, “Existence of words over a binary alphabet free from squares with mismatches”, Diskr. Mat., 30:2 (2018), 37–54; Discrete Math. Appl., 29:3 (2019), 175–188
Linking options:
https://www.mathnet.ru/eng/dm1473https://doi.org/10.4213/dm1473 https://www.mathnet.ru/eng/dm/v30/i2/p37
|
Statistics & downloads: |
Abstract page: | 311 | Full-text PDF : | 47 | References: | 31 | First page: | 12 |
|