×

zbMATH — the first resource for mathematics

Existence of words over a binary alphabet free from squares with mismatches. (English. Russian original) Zbl 07126264
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
PDF BibTeX XML Cite
Full Text: DOI
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
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.