Abstract:
The paper concerns some problems related to the existence of periodic structures in words from formal languages. Squares, i.e. fragments of the form $xx$, where $x$ is some word, and $\Delta$-squares, i.e. fragments of the form $xy$, where the word $x$ is different from the word $y$ by not more than $\Delta$ letters, are considered as periodic structures. We show the existence of arbitrarily long words over three-letter alphabet not containing $\Delta$-squares with the period exceeding $\Delta$. In particular, such words are constructed for all possible values $\Delta$.
Key words:Thue sequence, square-free words, word combinatorics, mismatches.
Fulltext:
PDF file (344 kB)