Avoidable patterns on two letters (Q1114419): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 03:16, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Avoidable patterns on two letters |
scientific article |
Statements
Avoidable patterns on two letters (English)
0 references
1989
0 references
We examine avoidable patterns, unavoidable in the sense of \textit{D. R. Bean}, \textit{A. Ehrenfeucht} and \textit{G. F. McNulty} [Pac. J. Math. 85, 261-294 (1979; Zbl 0428.05001)]. We prove that each pattern on two letters of length at least 13 is avoidable on an alphabet with two letters. The proof is based essentially on two facts: First, each pattern containing an overlapping factor is avoidable by the infinite word of Thue-Morse; secondly, each pattern without overlapping factor is avoidable by the infinite word of Fibonacci. We further discuss the minimal alphabet on which very short patterns on a 2-letter and a 3- letter alphabet are avoidable.
0 references
infinite Thue-Morse word
0 references
infinite Fibonacci word
0 references
combinatorics on words
0 references
avoidable patterns
0 references
alphabet with two letters
0 references
overlapping factor
0 references