Unavoidable binary patterns
From MaRDI portal
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.
Recommendations
Cites work
Cited in
(15)- Avoidable patterns on two letters
- On avoding \(r\)-repetitions in \(\mathbb R^2\)
- Some variations on a theme of Irina Mel'nichuk concerning the avoidability of patterns in strings of symbols
- Patterns in words and languages
- Binary words avoided by the Thue-Morse sequence
- On the aperiodic avoidability of binary patterns with variables and reversals
- Avoidability index for binary patterns with reversal
- scientific article; zbMATH DE number 6101325 (Why is no real title available?)
- scientific article; zbMATH DE number 4035171 (Why is no real title available?)
- Computing the partial word avoidability indices of ternary patterns
- Finite degrees of ambiguity in pattern languages
- Grasshopper avoidance of patterns
- Unavoidable sets of partial words
- Avoidable binary patterns in partial words
- A periodic division pattern that cannot be generated by D0L systems
This page was built for publication: Unavoidable binary patterns
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1323331)
