Geodesic
Existence of arbitrarily long square-free words with one possible mismatch
Diskretnaya Matematika, Tome 27 (2015) no. 2, pp. 56-72
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

We are concerned with problems of the existence of periodic structures in words from formal languages. We consider both squares (that is, fragments of the form $xx$, where $x$ is an arbitrary word) and squares with one mismatch (that is, fragments of the form $xy$, where a word $x$ differs from a word $y$ by exactly one letter). Given natural numbers $l_0$ and $l_1$, we study conditions for the existence of arbitrarily long words not containing squares with length larger than $l_0$ and squares with one mismatch and length larger than $l_1$. For all possible pairs $l_1\geq l_0$ a minimal alphabet cardinality is found which permits to construct such a word. \linebreak This research was carried out with the financial support of the Russian Foundation for Basic Research (grant no. 14-01-00598) and of the Branch of Mathematics of the Russian Academy of Sciences Program “Algebraic and combinatorial methods of mathematical cybernetics and new generation information systems” (the project “Problem of optimal synthesis of control systems”).
Keywords: Thue sequence, square-free words, word combinatorics, mismatch. 
@article{DM_2015_27_2_a3,
     author = {N. V. Kotlyarov},
     title = {Existence of arbitrarily long square-free words with one possible mismatch},
     journal = {Diskretnaya Matematika},
     pages = {56--72},
     year = {2015},
     volume = {27},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2015_27_2_a3/}
}
TY  - JOUR
AU  - N. V. Kotlyarov
TI  - Existence of arbitrarily long square-free words with one possible mismatch
JO  - Diskretnaya Matematika
PY  - 2015
SP  - 56
EP  - 72
VL  - 27
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/DM_2015_27_2_a3/
LA  - ru
ID  - DM_2015_27_2_a3
ER  - 
%0 Journal Article
%A N. V. Kotlyarov
%T Existence of arbitrarily long square-free words with one possible mismatch
%J Diskretnaya Matematika
%D 2015
%P 56-72
%V 27
%N 2
%U http://geodesic.mathdoc.fr/item/DM_2015_27_2_a3/
%G ru
%F DM_2015_27_2_a3
N. V. Kotlyarov. Existence of arbitrarily long square-free words with one possible mismatch. Diskretnaya Matematika, Tome 27 (2015) no. 2, pp. 56-72. http://geodesic.mathdoc.fr/item/DM_2015_27_2_a3/

[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, Per. s angl., M.: Mir, 1986

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

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

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

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