Avoidable patterns on two letters (Q1114419): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
(One intermediate revision by one other user not shown) | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0304-3975(89)90064-9 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2039659422 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Avoidable patterns in strings of symbols / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3860007 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3704906 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4529547 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: An O(n log n) algorithm for finding all repetitions in a string / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5646912 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: BLOCKING SETS OF TERMS / rank | |||
Normal rank |
Latest revision as of 10:36, 19 June 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