Existence of words over a binary alphabet free from squares with mismatches. (English. Russian original) Zbl 07126264

Kotlyarov, Nikita V.

Discrete Math. Appl. 29, No. 3, 175-188 (2019); translation from Diskretn. Mat. 30, No. 2, 37-54 (2018).

Summary: 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.

MSC:

68	Computer science
03	Mathematical logic and foundations

Keywords:

Thue sequence; square-free words; word combinatorics; mismatches

References:

[1]	Thue A., “Uber unendliche Zeichenreihen”, Mat. Nat. Kl. Khristiana, 7 (1906), 1-22. · JFM 39.0283.01
[2]	Salomaa A., Jewels of formal language theory, 1981, 144 pp. · Zbl 0487.68064
[3]	Thue A., “Uber die gegenseitige Lage gleicher Teile gewisser Zeichenreihen”, Mat. Nat. Kl. Kristiania, 1 (1912), 1-67. · JFM 43.0162.07
[4]	Fraenkel A. S., Simpson R. J., “How many squares must a binary sequence contain?”, Research Paper #R2, Electr. J. Comb., 2 (1995). · Zbl 0816.11007
[5]	Crochemore M., Ilie L., RytterW., “Repetitions in strings: algorithms and combinatorics”, Theor. Comput. Sci., 410(50) (2009), 5227-5235. · Zbl 1180.68206
[6]	Crochemore M., Rytter W., “Squares, cubes, and time-space efficient string searching”, Algorithmica, 13:5 (1995), 405-425. · Zbl 0849.68044
[7]	Kotlyarov N.V., “Existence of arbitrarily long square-free words with one possible mismatch”, Discrete Math. Appl., 25:6 (2015), 345-357. · Zbl 1345.68246
[8]	Kotlyarov N.V., “Square-free words with one possible mismatch”, 71:1, 31-34. · Zbl 1344.68180