zbMATH — the first resource for mathematics

Square-free words with one possible mismatch. (English. Russian original) Zbl 1344.68180
Mosc. Univ. Math. Bull. 71, No. 1, 31-34 (2016); translation from Vestn. Mosk. Univ., Ser. I 71, No. 1, 48-52 (2016).
A classical problem in combinatorics on words is, given a pattern \(p\), to decide what is the least size of an alphabet \(A\) such that there exist arbitrarily long words (or, equivalently, an infinite word) not containing \(p\). For example, A. Thue showed in 1906 that it is possible to construct an infinite word over an alphabet of three letters not containing squares, that is, factors of the form \(xx\), while it is readily verified that every sufficiently long word over a binary alphabet must contain a square. In this paper the author considers a new pattern that he calls “square with one error”, that is, a factor of the form \(xy\) where \(y\) differs from \(x\) in one letter. The paper announces several results (the proofs are omitted for space constraints) on the minimal size of the alphabet over which it is possible to construct infinite words not containing squares of half-length \(k_0\) and squares with one error of half-length \(k_1\), for all the possible combinations of \(k_0\) and \(k_1\).

68R15 Combinatorics on words
Full Text: DOI
[1] Thue, A., Uber unendliche zeichenreihen, Norske, Vid. Selsk. Skr. I, Mat. Nat. Kl. Khristiana, 7, 1, (1906) · JFM 39.0283.01
[2] A. Salomaa, Jewels of Formal Language Theory (Computer Science Press, 1981; Mir, Moscow, 1986). · Zbl 0487.68063
[3] Thue, A., Uber die gegenseitige lage gleicher teile gewisser zeichenreihen, Norske, Vid. Selsk. Skr. I, Mat. Nat. Kl. Kristiania, 1, 1, (1912) · JFM 44.0462.01
[4] Fraenkel, A. S.; Simpson, R. J., How many squares must a binary sequence contain?, Electr. J. Comb., 2, 12, (1995) · Zbl 0816.11007
[5] Crochemore, M.; Ilie, L.; Rytter, W., Repetitions in strings: algorithms and combinatorics, Theor. Comput. Sci., 410, 5227, (2009) · Zbl 1180.68206
[6] Crochemore, M.; Rytter, W., Squares, cubes, and time-space efficient string searching, Algorithmica, 13, 405, (1995) · Zbl 0849.68044
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.