In mathematics and theoretical computer science, a pattern is an unavoidable pattern if it is unavoidable on any finite alphabet.
Definitions
Pattern Like a word, a pattern (also called term) is a sequence of symbols over some alphabet. The minimum multiplicity of the pattern p {\displaystyle p} is m ( p ) = min ( c o u n t p ( x ) : x ∈ p ) {\displaystyle m(p)=\min(\mathrm {count_{p}} (x):x\in p)} where c o u n t p ( x ) {\displaystyle \mathrm {count_{p}} (x)} is the number of occurrence of symbol x {\displaystyle x} in pattern p {\displaystyle p} . In other words, it is the number of occurrences in p {\displaystyle p} of the least frequently occurring symbol in p {\displaystyle p} .
Instance Given finite alphabets Σ {\displaystyle \Sigma } and Δ {\displaystyle \Delta } , a word x ∈ Σ ∗ {\displaystyle x\in \Sigma ^{*}} is an instance of the pattern p ∈ Δ ∗ {\displaystyle p\in \Delta ^{*}} if there exists a non-erasing semigroup morphism f : Δ ∗ → Σ ∗ {\displaystyle f:\Delta ^{*}\rightarrow \Sigma ^{*}} such that f ( p ) = x {\displaystyle f(p)=x} , where Σ ∗ {\displaystyle \Sigma ^{*}} denotes the Kleene star of Σ {\displaystyle \Sigma } . Non-erasing means that f ( a ) ≠ ε {\displaystyle f(a)\neq \varepsilon } for all a ∈ Δ {\displaystyle a\in \Delta } , where ε {\displaystyle \varepsilon } denotes the empty string.
Avoidance / Matching A word w {\displaystyle w} is said to match, or encounter, a pattern p {\displaystyle p} if a factor (also called subword or substring) of w {\displaystyle w} is an instance of p {\displaystyle p} . Otherwise, w {\displaystyle w} is said to avoid p {\displaystyle p} , or to be p {\displaystyle p} -free. This definition can be generalized to the case of an infinite w {\displaystyle w} , based on a generalized definition of "substring".
Avoidability / Unavoidability on a specific alphabet A pattern p {\displaystyle p} is unavoidable on a finite alphabet Σ {\displaystyle \Sigma } if each sufficiently long word x ∈ Σ ∗ {\displaystyle x\in \Sigma ^{*}} must match p {\displaystyle p} ; formally: if ∃ n ∈ N . ∀ x ∈ Σ ∗ . ( | x | ≥ n ⟹ x matches p ) {\displaystyle \exists n\in \mathrm {N} .\ \forall x\in \Sigma ^{*}.\ (|x|\geq n\implies x{\text{ matches }}p)} . Otherwise, p {\displaystyle p} is avoidable on Σ {\displaystyle \Sigma } , which implies there exist infinitely many words over the alphabet Σ {\displaystyle \Sigma } that avoid p {\displaystyle p} . By Kőnig's lemma, pattern p {\displaystyle p} is avoidable on Σ {\displaystyle \Sigma } if and only if there exists an infinite word w ∈ Σ ω {\displaystyle w\in \Sigma ^{\omega }} that avoids p {\displaystyle p} .
… excerpt ends here. Continue reading the full article.
