Unavoidable pattern
In mathematics and theoretical computer science, an unavoidable pattern is a pattern of symbols that must occur in any sufficiently long string over an alphabet. An avoidable pattern is one for which there are infinitely many words no part of which match the pattern.
Let A be an alphabet of letters and E a disjoint alphabet of pattern symbols or "variables". Elements of E+ are patterns. For a pattern p, the pattern language is that subset of A∗ containing all words h(p) where h is a non-erasing semigroup morphism from the free monoid E∗ to A∗. A word w in A∗ matches or meets p if it contains some word in the pattern language as a factor, otherwise w avoids p.[1][2]
A pattern p is avoidable on A if there are infinitely many words in A∗ that avoid p; it is unavoidable on A if all sufficiently long words in A∗ match p. We say that p is k-unavoidable if it is unavoidable on every alphabet of size k and correspondingly k-unavoidable if it is avoidable on an alphabet of size k.[3][4]
There is a word W(k) over an alphabet of size 4k which avoids every avoidable pattern with less than 2k variables.[5]
Examples
- The Thue–Morse sequence avoids the patterns xxx and xyxyx.[3][4]
- The patterns x and xyx are unavoidable on any alphabet.[2][6]
- The power pattern xx is 3-avoidable;[3][2] words avoiding this pattern are square-free.[7][4]
- The power patterns xn for n ≥ 3 are 2-avoidable: the Thue–Morse sequence is an example for n=3.[3]
- Sesquipowers are unavoidable.[6]
Avoidability index
The avoidability index of a pattern p is the smallest k such that p is k-avoidable, or ∞ if p is unavoidable.[8] For binary patterns (two variables x and y) we have:[9]
- 1,x,xy,xyx are unavoidable;
- xx,xxy,xyy,xxyx,xxyy,xyxx,xyxy,xyyx,xxyxx,xxyxy,xyxyy have avoidability index 3;
- all other patterns have avoidability index 2.
Square-free words
A square-free word is one avoiding the pattern xx. An example is the word over the alphabet {0,±1} obtained by taking the first difference of the Thue–Morse sequence.[10][11]
References
- ^ Lothaire (2011) p. 112
- ^ a b c Allouche & Shallit (2003) p.24
- ^ a b c d Lothaire (2011) p. 113
- ^ a b c Berstel et al (2009) p.127
- ^ Lothaire (2011) p. 122
- ^ a b Lothaire (2011) p.115
- ^ Lothaire (2011) p. 114
- ^ Lothaire (2011) p.124
- ^ Lothaire (2011) p.126
- ^ Pytheas Fogg (2002) p.104
- ^ Berstel et al (2009) p.97
- Allouche, Jean-Paul; Shallit, Jeffrey (2003). Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press. ISBN 978-0-521-82332-6. Zbl 1086.11015.
- Berstel, Jean; Lauve, Aaron; Reutenauer, Christophe; Saliola, Franco V. (2009). Combinatorics on words. Christoffel words and repetitions in words. CRM Monograph Series. Vol. 27. Providence, RI: American Mathematical Society. ISBN 978-0-8218-4480-9. Zbl 1161.68043.
- Lothaire, M. (2011). Algebraic combinatorics on words. Encyclopedia of Mathematics and Its Applications. Vol. 90. With preface by Jean Berstel and Dominique Perrin (Reprint of the 2002 hardback ed.). Cambridge University Press. ISBN 978-0-521-18071-9. Zbl 1221.68183.
- Pytheas Fogg, N. (2002). Substitutions in dynamics, arithmetics and combinatorics. Lecture Notes in Mathematics. Vol. 1794. Editors Berthé, Valérie; Ferenczi, Sébastien; Mauduit, Christian; Siegel, A. Berlin: Springer-Verlag. ISBN 3-540-44141-7. Zbl 1014.11015.
 | This algebra-related article is a stub. You can help Wikipedia by expanding it. |