patrón inevitable

---

En matemáticas e informática teórica , un patrón es un patrón inevitable si es inevitable en cualquier alfabeto finito.

La multiplicidad mínima del patrón es donde está el número de ocurrencias del símbolo en el patrón . En otras palabras, es el número de ocurrencias del símbolo menos frecuente en . ${\ estilo de visualización p}$${\displaystyle m(p)=\min(\mathrm {contar_{p}} (x):x\in p)}$${\displaystyle \mathrm {contar_{p}} (x)}$${\ estilo de visualización x}$${\ estilo de visualización p}$${\ estilo de visualización p}$${\ estilo de visualización p}$

Dados los alfabetos finitos y , una palabra es una instancia del patrón si existe un morfismo de semigrupo que no se borra tal que , donde denota la estrella Kleene de . No borrar significa que para todos , donde denota la cadena vacía .${\ estilo de visualización \ Sigma}$${\ estilo de visualización \ Delta}$${\ estilo de visualización x \ en \ Sigma ^ {*}}$${\displaystyle p\en \Delta ^{*}}$ ${\displaystyle f:\Delta ^{*}\rightarrow \Sigma ^{*}}$${\ estilo de visualización f (p) = x}$${\ estilo de visualización \ Sigma ^ {*}}$${\ estilo de visualización \ Sigma}$${\ Displaystyle f (a) \ neq \ varepsilon}$${\ estilo de visualización a \ en \ Delta}$${\ estilo de visualización \ varepsilon}$

Se dice que una palabra coincide o encuentra un patrón si un factor (también llamado subpalabra o subcadena ) de es una instancia de . De lo contrario, se dice que evita o que está libre. Esta definición se puede generalizar al caso de un infinito , en función de una definición generalizada de "subcadena".${\ estilo de visualización w}$${\ estilo de visualización p}$${\ estilo de visualización w}$${\ estilo de visualización p}$${\ estilo de visualización w}$${\ estilo de visualización p}$${\ estilo de visualización p}$${\ estilo de visualización w}$

---