Some variations on a theme of Irina Mel'nichuk concerning the avoidability of patterns in strings of symbols (Q1753110)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Some variations on a theme of Irina Mel'nichuk concerning the avoidability of patterns in strings of symbols |
scientific article |
Statements
Some variations on a theme of Irina Mel'nichuk concerning the avoidability of patterns in strings of symbols (English)
0 references
25 May 2018
0 references
Assume two alphabets \(A\), \(B\). A word \(v\in A^{+}\) encounters a pattern \(w\in B^{+}\) if there is a morphism \(h:B^{+}\rightarrow A^{+}\) such that \(h(w)\) is a subword of \(v\). If \(v\) does not encounter \(w\) we say that \(v\) avoids \(w\). A pattern \(w\) (a set of patterns \(\Sigma\)) is avoidable on the alphabet with \(k\) letters provided there are infinitely many words on the \(k\)-letter alphabet each of which avoids \(w\) (avoids every pattern from \(\Sigma\)). A word \(w\) is doubled provided every letter that occurs in \(w\) occurs at least twice. There are several previous results on avoidability of doubled words. The current paper shows that the set of all doubled patterns on \(n=2m\), \(m\neq2,\) letters can be avoided on an alphabet with \(k=2m+2\) letters; the set of all doubled patterns on \(n=2m+1\) letters can be avoided on an alphabet with \(k=2m+4\) letters; the set of all doubled patterns on \(n=4\) letters can be avoided on an alphabet with \(8\) letters. Moreover, the set of all avoidable patterns on \(n\) letters can be avoided on an alphabet with \(k=2n+4\) letters.
0 references
avoidable words
0 references
doubled words
0 references
global avoidability
0 references
0 references