Existence of words over three-letter alphabet not containing squares with replacement errors.
(Existence of words over tree-letter alphabet not containing squares with replacement errors.)

*(English. Russian original)*Zbl 1408.68124
Mosc. Univ. Math. Bull. 73, No. 3, 90-97 (2018); translation from Vestn. Mosk. Univ., Ser. I 73, No. 3, 8-16 (2018).

The paper deals with a variant of avoidability of patterns in infinite words. The way the author deals with the basic terms is rather strange. He defines a well-established term, “factor”, as a fragment of a word, where his term “fragment” (undefined in the paper) seems to mean the common term “occurrence of the factor”. He makes the things even more obscure by stating that “factors can be represented in two ways, as word fragments, or as words”. This makes reading the paper rather difficult.

The author investigates avoidability of square factors with errors. He defines that an infinite word has the property \(\binom{\Delta}{p}\) if it does not contain factors of the form \(uv\), where \(|u|=|v| >p\geq0\) and \(v\) differs from \(u\) in at most \(\Delta\geq0\) letter positions (contains at most \(\Delta\) errors). The result of the paper states that for any \(\Delta\geq0\) there exists an infinite word over a three-letter alphabet possessing the property \(\binom{\Delta}{\Delta}\).

The author investigates avoidability of square factors with errors. He defines that an infinite word has the property \(\binom{\Delta}{p}\) if it does not contain factors of the form \(uv\), where \(|u|=|v| >p\geq0\) and \(v\) differs from \(u\) in at most \(\Delta\geq0\) letter positions (contains at most \(\Delta\) errors). The result of the paper states that for any \(\Delta\geq0\) there exists an infinite word over a three-letter alphabet possessing the property \(\binom{\Delta}{\Delta}\).

Reviewer: Anton Černý (Safat)

##### MSC:

68R15 | Combinatorics on words |

PDF
BibTeX
XML
Cite

\textit{N. V. Kotlyarov}, Mosc. Univ. Math. Bull. 73, No. 3, 90--97 (2018; Zbl 1408.68124); translation from Vestn. Mosk. Univ., Ser. I 73, No. 3, 8--16 (2018)

Full Text:
DOI

##### References:

[1] | Thue, A., Uber unendliche zeichenreihen, Mat. Nat. KL Khristiania, 7, 1, (1906) · JFM 39.0283.01 |

[2] | A. Salomaa, Jewels of Formal Language Theory (Computer Science Press, 1981; Mir, Moscow, 1986) · Zbl 0487.68064 |

[3] | Thue, A., Uber die gegenseitige lage gleicher teile gewisser zeichenreihen, Mat. Nat. KL Kristiania, 1, 1, (1912) · JFM 44.0462.01 |

[4] | S. Aviezri, “How Many Squares Must a Binary Sequence Contain?” Electron. J. Combinatorics 2 (1995). · Zbl 0816.11007 |

[5] | Crochemore, M., Repetitions in strings: algorithms and combinatorics, Theor. Comput. Sei., 410, 5227, (2009) · Zbl 1180.68206 |

[6] | Crochemore, M., Squares, cubes, and time-S pace efficient string searching, Algorithmica, 13, 405, (1995) · Zbl 0849.68044 |

[7] | Kotlyarov, N. V., Existence of arbitrarily long words not containing squares with one possible mismatch, Diskret. Matem., 27, 56, (2015) |

[8] | Kotlyarov, N. V., Square-free words with one possible mismatch, Vestn. Mosk, Univ., Matem. Mekhan., 1, 48, (2016) · 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.