Avoidable patterns on two letters
type: Item
instance of: scholarly article
title: Avoidable patterns on two letters
zbMATH Open document ID: 0662.68078
DOI: 10.1016/0304-3975(89)90064-9
author: Ursula Schmidt
published in: Theoretical Computer Science
publication date: 1989-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 05A05
Mathematics Subject Classification ID: 05A99
Mathematics Subject Classification ID: 20M05
zbMATH DE Number: 4083009
zbMATH Keywords: infinite Thue-Morse word
zbMATH Keywords: infinite Fibonacci word
zbMATH Keywords: combinatorics on words
zbMATH Keywords: avoidable patterns
zbMATH Keywords: alphabet with two letters
zbMATH Keywords: overlapping factor
MaRDI profile type: Publication
full work available at URL: 0304-3975(89)90064-9
OpenAlex ID: W2039659422
cites work: Avoidable patterns in strings of symbols
cites work: Q3860007
cites work: Q3704906
cites work: Q4529547
cites work: An O(n log n) algorithm for finding all repetitions in a string
cites work: Q5646912
cites work: BLOCKING SETS OF TERMS
description: scientific article; zbMATH DE number 4083009