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/

[1] Thue A., “Uber unendliche Zeichenreihen”, Mat. Nat. Kl. Khristiana, 7 (1906), 1–22

[2] Salomaa A., Jewels of formal language theory, 1981, 144 pp. | MR | MR

[3] Thue A., “Uber die gegenseitige Lage gleicher Teile gewisser Zeichenreihen”, Mat. Nat. Kl. Kristiania, 1 (1912), 1–67 | Zbl

[4] Fraenkel A. S., Simpson R. J., “How many squares must a binary sequence contain?”, Research Paper #R2, Electr. J. Comb., 2 (1995) | MR

[5] Crochemore M., Ilie L., Rytter W., “Repetitions in strings: algorithms and combinatorics”, Theor. Comput. Sci., 410(50) (2009), 5227–5235 | DOI | MR | Zbl

[6] Crochemore M., Rytter W., “Squares, cubes, and time-space efficient string searching”, Algorithmica, 13:5 (1995), 405–425 | DOI | MR | Zbl

[7] Kotlyarov N.V., “Existence of arbitrarily long square-free words with one possible mismatch”, Discrete Math. Appl., 25:6 (2015), 345–357 | DOI | DOI | MR | Zbl

[8] Kotlyarov N.V., “Square-free words with one possible mismatch”, 71, no. 1, 31–34 | MR | Zbl