zbMATH — the first resource for mathematics

Existence of arbitrarily long square-free words with one possible mismatch. (English. Russian original) Zbl 1345.68246
Discrete Math. Appl. 25, No. 6, 345-357 (2015); translation from Diskretn. Mat. 27, No. 2, 56-72 (2015).
Summary: 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.

68R15 Combinatorics on words
68Q45 Formal languages and automata
Full Text: DOI