Geodesic
Square-free words with one possible mismatch
Vestnik Moskovskogo universiteta. Matematika, mehanika, no. 1 (2016), pp. 48-52 
N. V. Kotlyarov. Square-free words with one possible mismatch. Vestnik Moskovskogo universiteta. Matematika, mehanika, no. 1 (2016), pp. 48-52. http://geodesic.mathdoc.fr/item/VMUMM_2016_1_a7/
@article{VMUMM_2016_1_a7,
     author = {N. V. Kotlyarov},
     title = {Square-free words with one possible mismatch},
     journal = {Vestnik Moskovskogo universiteta. Matematika, mehanika},
     pages = {48--52},
     year = {2016},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VMUMM_2016_1_a7/}
}
TY  - JOUR
AU  - N. V. Kotlyarov
TI  - Square-free words with one possible mismatch
JO  - Vestnik Moskovskogo universiteta. Matematika, mehanika
PY  - 2016
SP  - 48
EP  - 52
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/VMUMM_2016_1_a7/
LA  - ru
ID  - VMUMM_2016_1_a7
ER  - 
%0 Journal Article
%A N. V. Kotlyarov
%T Square-free words with one possible mismatch
%J Vestnik Moskovskogo universiteta. Matematika, mehanika
%D 2016
%P 48-52
%N 1
%U http://geodesic.mathdoc.fr/item/VMUMM_2016_1_a7/
%G ru
%F VMUMM_2016_1_a7

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

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.

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

[2] Salomaa A., Zhemchuzhiny teorii formalnykh yazykov, Mir, M., 1986 | MR

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

[4] Fraenkel A.S., Simpson R.J., How many squares must a binary sequence contain?, Electr. J. Comb., 2 (1995), 12–16 | 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