# 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.

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