Unavoidable binary patterns
type: Item
instance of: scholarly article
title: Unavoidable binary patterns
zbMATH Open document ID: 0790.68096
DOI: 10.1007/BF01209712
author: Julien Cassaigne
published in: Acta Informatica
publication date: 1993-01-01T00:00:00Z
review text: Peter Roth proved that there are no binary patterns of length six or more that are unavoidable on the two-letter alphabet. He gave an almost complete description of unavoidable binary patterns. In this paper we prove one of his conjectures: the pattern \(\alpha^ 2\beta^ 2\alpha\) is 2-avoidable. From this we deduce the complete classification of unavoidable binary patterns. We also study the concept of avoidability by iterated morphisms and prove that there are a few 2-avoidable patterns which are not avoided by any iterated morphism.
Mathematics Subject Classification ID: 68R15
zbMATH DE Number: 567297
zbMATH Keywords: unavoidable binary patterns
zbMATH Keywords: avoidability by iterated morphisms
MaRDI profile type: Publication
cites work: Growth problems for avoidable words
cites work: Avoidable patterns in strings of symbols
cites work: Every binary pattern of length six is avoidable on the two-letter alphabet
cites work: Q3948609
cites work: Avoidable patterns on two letters
cites work: BLOCKING SETS OF TERMS
description: scientific article; zbMATH DE number 567297