Geodesic
Existence of words over a binary alphabet free from squares with mismatches
Diskretnaya Matematika, Tome 30 (2018) no. 2, pp. 37-54

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{DM_2018_30_2_a3,
     author = {N. V. Kotlyarov},
     title = {Existence of words over a binary alphabet free from squares with mismatches},
     journal = {Diskretnaya Matematika},
     pages = {37--54},
     publisher = {mathdoc},
     volume = {30},
     number = {2},
     year = {2018},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2018_30_2_a3/}
}
TY  - JOUR
AU  - N. V. Kotlyarov
TI  - Existence of words over a binary alphabet free from squares with mismatches
JO  - Diskretnaya Matematika
PY  - 2018
SP  - 37
EP  - 54
VL  - 30
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2018_30_2_a3/
LA  - ru
ID  - DM_2018_30_2_a3
ER  - 
%0 Journal Article
%A N. V. Kotlyarov
%T Existence of words over a binary alphabet free from squares with mismatches
%J Diskretnaya Matematika
%D 2018
%P 37-54
%V 30
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2018_30_2_a3/
%G ru
%F DM_2018_30_2_a3
N. V. Kotlyarov. Existence of words over a binary alphabet free from squares with mismatches. Diskretnaya Matematika, Tome 30 (2018) no. 2, pp. 37-54. http://geodesic.mathdoc.fr/item/DM_2018_30_2_a3/