Abstract:
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.
Keywords:Thue sequence, square-free words, word combinatorics, mismatches.
Fulltext:
PDF file (805 kB)