Difference between revisions of "Unavoidable pattern"
(Start article: Unavoidable pattern) |
m (→References: isbn) |
||
(2 intermediate revisions by one other user not shown) | |||
Line 1: | Line 1: | ||
+ | {{TEX|done}}{{MSC|68R15}} | ||
A pattern of symbols that must occur in any sufficiently long [[word]] over a given alphabet. An '''avoidable pattern''' is one which for which there are infinitely many words no part of which match the pattern. | A pattern of symbols that must occur in any sufficiently long [[word]] over a given alphabet. An '''avoidable pattern''' is one which for which there are infinitely many words no part of which match the pattern. | ||
Line 4: | Line 5: | ||
Let $A$ be an alphabet of letters and $E$ a disjoint alphabet of pattern symbols or "variables". Elements of the [[Free semi-group|free semigroup]] of non-empty words $E^+$ are ''patterns''. For a pattern $p$, the pattern language is that subset of the [[free monoid]] $A^*$ containing all words $h(p)$ where $h$ is a non-erasing [[semigroup morphism]] from $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$. | Let $A$ be an alphabet of letters and $E$ a disjoint alphabet of pattern symbols or "variables". Elements of the [[Free semi-group|free semigroup]] of non-empty words $E^+$ are ''patterns''. For a pattern $p$, the pattern language is that subset of the [[free monoid]] $A^*$ containing all words $h(p)$ where $h$ is a non-erasing [[semigroup morphism]] from $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$. | ||
− | A pattern $p$ is ''avoidable'' on $A$ if there are infinitely many words in $A^*$ that avoid | + | 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$-avoidable if it is avoidable on an alphabet of size $k$. |
There is a word $W(k)$ over an alphabet of size $4k$ which avoids every avoidable pattern with fewer than $2k$ variables. | There is a word $W(k)$ over an alphabet of size $4k$ which avoids every avoidable pattern with fewer than $2k$ variables. | ||
Line 27: | Line 28: | ||
====References==== | ====References==== | ||
− | * Allouche, Jean-Paul; Shallit, Jeffrey; "Automatic Sequences: Theory, Applications, Generalizations" Cambridge University Press (2003) | + | * Allouche, Jean-Paul; Shallit, Jeffrey; "Automatic Sequences: Theory, Applications, Generalizations" Cambridge University Press (2003) {{ISBN|978-0-521-82332-6}} {{ZBL|1086.11015}} |
− | * Berstel, Jean; Lauve, Aaron; Reutenauer, Christophe; Saliola, Franco V.; "Combinatorics on words. Christoffel words and repetitions in words", CRM Monograph Series '''27''' American Mathematical Society (2009) ISBN 978-0-8218-4480-9 {{ZBL|1161.68043}} | + | * Berstel, Jean; Lauve, Aaron; Reutenauer, Christophe; Saliola, Franco V.; "Combinatorics on words. Christoffel words and repetitions in words", CRM Monograph Series '''27''' American Mathematical Society (2009) {{ISBN|978-0-8218-4480-9}} {{ZBL|1161.68043}} |
− | * Lothaire, M.; "Algebraic combinatorics on words", Encyclopedia of Mathematics and Its Applications '''90'''Cambridge University Press (2011) ISBN 978-0-521-18071-9 {{ZBL|1221.68183}} | + | * Lothaire, M.; "Algebraic combinatorics on words", Encyclopedia of Mathematics and Its Applications '''90'''Cambridge University Press (2011) {{ISBN|978-0-521-18071-9}} {{ZBL|1221.68183}} |
− | * Pytheas Fogg, N.; "Substitutions in dynamics, arithmetics and combinatorics" Lecture Notes in Mathematics '''1794''' Springer-Verlag (2002) ISBN 3-540-44141-7 {{ZBL|1014.11015 | + | * Pytheas Fogg, N.; "Substitutions in dynamics, arithmetics and combinatorics" Lecture Notes in Mathematics '''1794''' Springer-Verlag (2002) {{ISBN|3-540-44141-7}} {{ZBL|1014.11015}} |
− | |||
− |
Latest revision as of 20:18, 7 November 2023
2020 Mathematics Subject Classification: Primary: 68R15 [MSN][ZBL]
A pattern of symbols that must occur in any sufficiently long word over a given alphabet. An avoidable pattern is one which 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 the free semigroup of non-empty words $E^+$ are patterns. For a pattern $p$, the pattern language is that subset of the free monoid $A^*$ containing all words $h(p)$ where $h$ is a non-erasing semigroup morphism from $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$.
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$-avoidable if it is avoidable on an alphabet of size $k$.
There is a word $W(k)$ over an alphabet of size $4k$ which avoids every avoidable pattern with fewer than $2k$ variables.
Examples
- The Thue–Morse sequence avoids the patterns $xxx$ and $xyxyx$.
- The patterns $x$ and $xyx$ are unavoidable on any alphabet.
- The power pattern $xx$ is 3-avoidable; words avoiding this pattern are square-free.
- The power patterns $x^n$ for $n \ge 3$ are 2-avoidable: the Thue–Morse sequence is an example for $n=3$.
- Sesquipowers are unavoidable.
Avoidability index
The avoidability index of a pattern $p$ is the smallest $k$ such that $p$ is $k$-avoidable, or $\infty$ if $p$ is unavoidable. For binary patterns (two variables $x$ and $y$) we have:
- $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,\pm1\}$ obtained by taking the first difference of the Thue–Morse sequence.
References
- Allouche, Jean-Paul; Shallit, Jeffrey; "Automatic Sequences: Theory, Applications, Generalizations" Cambridge University Press (2003) ISBN 978-0-521-82332-6 Zbl 1086.11015
- Berstel, Jean; Lauve, Aaron; Reutenauer, Christophe; Saliola, Franco V.; "Combinatorics on words. Christoffel words and repetitions in words", CRM Monograph Series 27 American Mathematical Society (2009) ISBN 978-0-8218-4480-9 Zbl 1161.68043
- Lothaire, M.; "Algebraic combinatorics on words", Encyclopedia of Mathematics and Its Applications 90Cambridge University Press (2011) ISBN 978-0-521-18071-9 Zbl 1221.68183
- Pytheas Fogg, N.; "Substitutions in dynamics, arithmetics and combinatorics" Lecture Notes in Mathematics 1794 Springer-Verlag (2002) ISBN 3-540-44141-7 Zbl 1014.11015
Unavoidable pattern. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Unavoidable_pattern&oldid=39623