Patrón inevitable

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

Definiciones

Patrón

Al igual que una palabra, un patrón (también llamado término ) es una secuencia de símbolos sobre algún alfabeto .

La multiplicidad mínima del patrón es donde es el número de ocurrencias del símbolo en el patrón . En otras palabras, es el número de ocurrencias en del símbolo que ocurre con menor frecuencia en . ${\displaystyle p}$ ${\displaystyle m(p)=\min(\mathrm {count_{p}} (x):x\in p)}$ ${\displaystyle \mathrm {count_{p}} (x)}$ ${\displaystyle x}$ ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle p}$

Instancia

Dados 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 de Kleene de . No borrable significa que para todos los , donde denota la cadena vacía . ${\displaystyle \Sigma }$ ${\displaystyle \Delta }$ ${\displaystyle x\in \Sigma ^{*}}$ ${\displaystyle p\in \Delta ^{*}}$ ${\displaystyle f:\Delta ^{*}\rightarrow \Sigma ^{*}}$ ${\displaystyle f(p)=x}$ ${\displaystyle \Sigma ^{*}}$ ${\displaystyle \Sigma }$ ${\displaystyle f(a)\neq \varepsilon }$ ${\displaystyle a\in \Delta }$ ${\displaystyle \varepsilon }$

Evitación / Coincidencia

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 es libre de . Esta definición se puede generalizar al caso de un infinito , basándose en una definición generalizada de "subcadena". ${\displaystyle w}$ ${\displaystyle p}$ ${\displaystyle w}$ ${\displaystyle p}$ ${\displaystyle w}$ ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle w}$

Evitabilidad / Inevitabilidad en un alfabeto específico

Un patrón es inevitable en un alfabeto finito si cada palabra suficientemente larga debe coincidir con ; formalmente: si . De lo contrario, es evitable en , lo que implica que existen infinitas palabras en el alfabeto que evitan . ${\displaystyle p}$ ${\displaystyle \Sigma }$ ${\displaystyle x\in \Sigma ^{*}}$ ${\displaystyle p}$ ${\displaystyle \exists n\in \mathrm {N} .\ \forall x\in \Sigma ^{*}.\ (|x|\geq n\implies x{\text{ matches }}p)}$ ${\displaystyle p}$ ${\displaystyle \Sigma }$ ${\displaystyle \Sigma }$ ${\displaystyle p}$

Según el lema de König , el patrón es evitable en si y sólo si existe una palabra infinita que evita . ^[1] ${\displaystyle p}$ ${\displaystyle \Sigma }$ ${\displaystyle w\in \Sigma ^{\omega }}$ ${\displaystyle p}$

Máximopag-palabra libre

Dado un patrón y un alfabeto , una palabra libre es una palabra libre máxima si y coincide . ${\displaystyle p}$ ${\displaystyle \Sigma }$ ${\displaystyle p}$ ${\displaystyle w\in \Sigma ^{*}}$ ${\displaystyle p}$ ${\displaystyle \Sigma }$ ${\displaystyle aw}$ ${\displaystyle wa}$ ${\displaystyle p}$ ${\displaystyle \forall a\in \Sigma }$

Patrón evitable/inevitable

Un patrón es un patrón inevitable (también llamado término de bloqueo ) si es inevitable en cualquier alfabeto finito. ${\displaystyle p}$ ${\displaystyle p}$

Si un patrón es inevitable y no se limita a un alfabeto específico, entonces es inevitable para cualquier alfabeto finito por defecto. Por el contrario, si se dice que un patrón es evitable y no se limita a un alfabeto específico, entonces es evitable en algún alfabeto finito por defecto.

a-evitable /a-inevitable

Un patrón es -evitable si es evitable en un alfabeto de tamaño . De lo contrario, es -inevitable, lo que significa que es inevitable en todo alfabeto de tamaño . ^[2] ${\displaystyle p}$ ${\displaystyle k}$ ${\displaystyle p}$ ${\displaystyle \Sigma }$ ${\displaystyle k}$ ${\displaystyle p}$ ${\displaystyle k}$ ${\displaystyle p}$ ${\displaystyle k}$

Si el patrón es -evitable, entonces es -evitable para todos los . ${\displaystyle p}$ ${\displaystyle k}$ ${\displaystyle p}$ ${\displaystyle g}$ ${\displaystyle g\geq k}$

Dado un conjunto finito de patrones evitables , existe una palabra infinita tal que evita todos los patrones de . ^[1] Sea el tamaño del alfabeto mínimo tal que evita todos los patrones de . ${\displaystyle S=\{p_{1},p_{2},...,p_{i}\}}$ ${\displaystyle w\in \Sigma ^{\omega }}$ ${\displaystyle w}$ ${\displaystyle S}$ ${\displaystyle \mu (S)}$ ${\displaystyle \Sigma '}$ ${\displaystyle \exists w'\in {\Sigma '}^{\omega }}$ ${\displaystyle S}$

Índice de evitabilidad

El índice de evitabilidad de un patrón es el más pequeño tal que es -evitable, y si es inevitable. ^[1] ${\displaystyle p}$ ${\displaystyle k}$ ${\displaystyle p}$ ${\displaystyle k}$ ${\displaystyle \infty }$ ${\displaystyle p}$

Propiedades

• Un patrón es evitable si es una instancia de un patrón evitable . ^[3] ${\displaystyle q}$ ${\displaystyle q}$ ${\displaystyle p}$
• Sea el patrón evitable un factor del patrón , entonces también es evitable. ^[3] ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle q}$
• Un patrón es inevitable si y sólo si es un factor de algún patrón inevitable . ${\displaystyle q}$ ${\displaystyle q}$ ${\displaystyle p}$
• Dado un patrón inevitable y un símbolo que no está en , entonces es inevitable. ^[3] ${\displaystyle p}$ ${\displaystyle a}$ ${\displaystyle p}$ ${\displaystyle pap}$
• Dado un patrón inevitable , entonces la reversión es inevitable. ${\displaystyle p}$ ${\displaystyle p^{R}}$
• Dado un patrón inevitable , existe un símbolo tal que aparece exactamente una vez en . ^[3] ${\displaystyle p}$ ${\displaystyle a}$ ${\displaystyle a}$ ${\displaystyle p}$
• Sea el número de símbolos distintos del patrón . Si , entonces es evitable. ^[3] ${\displaystyle n\in \mathrm {N} }$ ${\displaystyle p}$ ${\displaystyle |p|\geq 2^{n}}$ ${\displaystyle p}$

Palabras de Zimin

Dado el alfabeto , las palabras Zimin (patrones) se definen recursivamente para y . ${\displaystyle \Delta =\{x_{1},x_{2},...\}}$ ${\displaystyle Z_{n+1}=Z_{n}x_{n+1}Z_{n}}$ ${\displaystyle n\in \mathrm {Z} ^{+}}$ ${\displaystyle Z_{1}=x_{1}}$

Inevitabilidad

Todas las palabras de Zimin son inevitables. ^[4]

Una palabra es inevitable si y sólo si es un factor de una palabra Zimin. ^[4] ${\displaystyle w}$

Dado un alfabeto finito , sea , el más pequeño que coincida con todos los . Tenemos las siguientes propiedades: ^[5] ${\displaystyle \Sigma }$ ${\displaystyle f(n,|\Sigma |)}$ ${\displaystyle m\in \mathrm {Z} ^{+}}$ ${\displaystyle w}$ ${\displaystyle Z_{n}}$ ${\displaystyle w\in \Sigma ^{m}}$

• ${\displaystyle f(1,q)=1}$
• ${\displaystyle f(2,q)=2q+1}$
• ${\displaystyle f(3,2)=29}$
• ${\displaystyle f(n,q)\leq {^{n-1}q}=\underbrace {q^{q^{\cdot ^{\cdot ^{q}}}}} _{n-1}}$

${\displaystyle Z_{n}}$es el patrón inevitable más largo construido por el alfabeto desde . ${\displaystyle \Delta =\{x_{1},x_{2},...,x_{n}\}}$ ${\displaystyle |Z_{n}|=2^{n}-1}$

Reducción de patrones

Carta gratis

Dado un patrón sobre algún alfabeto , decimos que es libre si existen subconjuntos de tales que se cumple lo siguiente: ${\displaystyle p}$ ${\displaystyle \Delta }$ ${\displaystyle x\in \Delta }$ ${\displaystyle p}$ ${\displaystyle A,B}$ ${\displaystyle \Delta }$

1. ${\displaystyle uv}$es un factor de y ↔ es un factor de y ${\displaystyle p}$ ${\displaystyle u\in A}$ ${\displaystyle uv}$ ${\displaystyle p}$ ${\displaystyle v\in B}$
2. ${\displaystyle x\in A\backslash B\cup B\backslash A}$

Por ejemplo, sea , entonces es libre porque existen que satisfacen las condiciones anteriores. ${\displaystyle p=abcbab}$ ${\displaystyle b}$ ${\displaystyle p}$ ${\displaystyle A=ac,B=b}$

Reducir

Un patrón se reduce a patrón si existe un símbolo tal que esté libre para , y se puede obtener eliminando todas las ocurrencias de de . Denotemos esta relación por . ${\displaystyle p\in \Delta ^{*}}$ ${\displaystyle q}$ ${\displaystyle x\in \Delta }$ ${\displaystyle x}$ ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle x}$ ${\displaystyle p}$ ${\displaystyle p{\stackrel {x}{\rightarrow }}q}$

Por ejemplo, sea , entonces se puede reducir a ya que es libre para . ${\displaystyle p=abcbab}$ ${\displaystyle p}$ ${\displaystyle q=aca}$ ${\displaystyle b}$ ${\displaystyle p}$

Bloqueado

Se dice que una palabra está bloqueada si no tiene ninguna letra libre; por lo tanto, no se puede reducir. ^[6] ${\displaystyle w}$ ${\displaystyle w}$ ${\displaystyle w}$

Transitividad

Dados los patrones , si se reduce a y se reduce a , entonces se reduce a . Denotemos esta relación por . ${\displaystyle p,q,r}$ ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle q}$ ${\displaystyle r}$ ${\displaystyle p}$ ${\displaystyle r}$ ${\displaystyle p{\stackrel {*}{\rightarrow }}r}$

Inevitabilidad

Un patrón es inevitable si y sólo si se reduce a una palabra de longitud uno; por lo tanto, tal que y . ^{[7] [4]} ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle \exists w}$ ${\displaystyle |w|=1}$ ${\displaystyle p{\stackrel {*}{\rightarrow }}w}$

Evitar patrones gráficos[8]

Evitación/Coincidencia en un gráfico específico

Dado un gráfico simple , una coloración de aristas coincide con un patrón si existe un camino simple en tal que la secuencia coincida con . De lo contrario, se dice que se evita o es libre. ${\displaystyle G=(V,E)}$ ${\displaystyle c:E\rightarrow \Delta }$ ${\displaystyle p}$ ${\displaystyle P=[e_{1},e_{2},...,e_{r}]}$ ${\displaystyle G}$ ${\displaystyle c(P)=[c(e_{1}),c(e_{2}),...,c(e_{r})]}$ ${\displaystyle p}$ ${\displaystyle c}$ ${\displaystyle p}$ ${\displaystyle p}$

De manera similar, un patrón de coloración de vértice coincide si existe una ruta simple en tal que la secuencia coincide . ${\displaystyle c:V\rightarrow \Delta }$ ${\displaystyle p}$ ${\displaystyle P=[c_{1},c_{2},...,c_{r}]}$ ${\displaystyle G}$ ${\displaystyle c(P)}$ ${\displaystyle p}$

Número cromático del patrón

El número cromático del patrón es el número mínimo de colores distintos necesarios para una coloración de vértice libre sobre el gráfico . ${\displaystyle \pi _{p}(G)}$ ${\displaystyle p}$ ${\displaystyle c}$ ${\displaystyle G}$

Sea donde es el conjunto de todos los gráficos simples con un grado máximo no mayor que . ${\displaystyle \pi _{p}(n)=\max\{\pi _{p}(G):G\in G_{n}\}}$ ${\displaystyle G_{n}}$ ${\displaystyle n}$

De manera similar, y se definen para coloraciones de bordes. ${\displaystyle \pi _{p}'(G)}$ ${\displaystyle \pi _{p}'(n)}$

Evitabilidad / Inevitabilidad en gráficos

Un patrón se puede evitar en los gráficos si está limitado por , donde solo depende de . ${\displaystyle p}$ ${\displaystyle \pi _{p}(n)}$ ${\displaystyle c_{p}}$ ${\displaystyle c_{p}}$ ${\displaystyle p}$

• La evitación de palabras se puede expresar como un caso específico de evitación de gráficos; por lo tanto, un patrón es evitable en cualquier alfabeto finito si y solo si para todo , donde es un gráfico de vértices concatenados. ${\displaystyle p}$ ${\displaystyle \pi _{p}(P_{n})\leq c_{p}}$ ${\displaystyle n\in \mathrm {Z} ^{+}}$ ${\displaystyle P_{n}}$ ${\displaystyle n}$

Límite probabilístico enπ p (n)

Existe una constante absoluta , tal que para todos los patrones con . ^[8] ${\displaystyle c}$ ${\displaystyle \pi _{p}(n)\leq cn^{\frac {m(p)}{m(p)-1}}\leq cn^{2}}$ ${\displaystyle p}$ ${\displaystyle m(p)\geq 2}$

Dado un patrón , represente la cantidad de símbolos distintos de . Si , entonces es evitable en gráficos. ${\displaystyle p}$ ${\displaystyle n}$ ${\displaystyle p}$ ${\displaystyle |p|\geq 2^{n}}$ ${\displaystyle p}$

Coloraciones explícitas

Dado un patrón tal que sea par para todos , entonces para todos , donde es el gráfico completo de vértices. ^[8] ${\displaystyle p}$ ${\displaystyle count_{p}(x)}$ ${\displaystyle x\in p}$ ${\displaystyle \pi _{p}'(K_{2}^{k})\leq 2^{k}-1}$ ${\displaystyle k\geq 1}$ ${\displaystyle K_{n}}$ ${\displaystyle n}$

Dado un patrón tal que , y un árbol arbitrario , sea el conjunto de todos los subpatrones evitables y sus reflejos de . Entonces . ^[8] ${\displaystyle p}$ ${\displaystyle m(p)\geq 2}$ ${\displaystyle T}$ ${\displaystyle S}$ ${\displaystyle p}$ ${\displaystyle \pi _{p}(T)\leq 3\mu (S)}$

Dado un patrón tal que , y un árbol con grado . Sea el conjunto de todos los subpatrones evitables y sus reflejos de , entonces . ^[8] ${\displaystyle p}$ ${\displaystyle m(p)\geq 2}$ ${\displaystyle T}$ ${\displaystyle n\geq 2}$ ${\displaystyle S}$ ${\displaystyle p}$ ${\displaystyle \pi _{p}'(T)\leq 2(n-1)\mu (S)}$

Ejemplos

• La secuencia de Thue-Morse no tiene cubos ni superposiciones, por lo que evita los patrones y . ^[2] ${\displaystyle xxx}$ ${\displaystyle xyxyx}$
• Una palabra sin cuadrados es aquella que evita el patrón . La palabra sobre el alfabeto obtenida tomando la primera diferencia de la secuencia de Thue-Morse es un ejemplo de una palabra infinita sin cuadrados. ^{[9] [10]} ${\displaystyle xx}$ ${\displaystyle \{0,\pm 1\}}$
• Los patrones son inevitables en cualquier alfabeto, ya que son factores de las palabras Zimin. ^{[11] [1]} ${\displaystyle x}$ ${\displaystyle xyx}$
• Los patrones de potencia son 2-evitables. ^[1] ${\displaystyle x^{n}}$ ${\displaystyle n\geq 3}$
• Todos los patrones binarios se pueden dividir en tres categorías: ^[1]
  • ${\displaystyle \varepsilon ,x,xyx}$son inevitables.
  • ${\displaystyle xx,xxy,xyy,xxyx,xxyy,xyxx,xyxy,xyyx,xxyxx,xxyxy,xyxyy}$tienen un índice de evitabilidad de 3.
  • otros tienen un índice de evitabilidad de 2.
• ${\displaystyle abwbaxbcyaczca}$tiene un índice de evitabilidad de 4, al igual que otras palabras bloqueadas. ^[6]
• ${\displaystyle abvacwbaxbcycdazdcd}$tiene un índice de evitabilidad de 5. ^[12]
• El umbral repetitivo es el ínfimo de exponentes que se puede evitar en un alfabeto de tamaño . Véase también el teorema de Dejean . ${\displaystyle RT(n)}$ ${\displaystyle k}$ ${\displaystyle x^{k}}$ ${\displaystyle n}$

Problemas abiertos

• ¿Existe un patrón evitable tal que el índice de evitabilidad sea 6? ${\displaystyle p}$ ${\displaystyle p}$
• Dado un patrón arbitrario , ¿existe un algoritmo para determinar el índice de evitabilidad de ? ^[1] ${\displaystyle p}$ ${\displaystyle p}$

Referencias

1. Lothaire, M. (2002). Combinatoria algebraica en palabras . Cambridge University Press. ISBN 9780521812207.
2. Combinatoria de palabras: palabras de Christoffel y repeticiones en palabras. American Mathematical Soc. p. 127. ISBN 978-0-8218-7325-0.
3. Schmidt, Ursula (1987-08-01). "Patrones largos inevitables". Acta Informatica . 24 (4): 433–445. doi :10.1007/BF00292112. ISSN  1432-0525. S2CID  7928450.
4. Zimin, AI (1984). "Bloqueo de conjuntos de términos". Matemáticas de la URSS-Sbornik . 47 (2): 353–364. Código Bibliográfico :1984SbMat..47..353Z. doi :10.1070/SM1984v047n02ABEH002647. ISSN  0025-5734.
5. Joshua, Cooper; Rorabaugh, Danny (2013). Límites para evitar palabras en Zimin. arXiv : 1409.3080 . Código Bibliográfico :2014arXiv1409.3080C.
6. Baker, Kirby A.; McNulty, George F.; Taylor, Walter (1989-12-18). "Problemas de crecimiento para palabras evitables". Ciencias Informáticas Teóricas . 69 (3): 319–345. doi : 10.1016/0304-3975(89)90071-6 . ISSN  0304-3975.
7. Bean, Dwight R.; Ehrenfeucht, Andrzej; McNulty, George F. (1979). "Patrones evitables en cadenas de símbolos". Revista del Pacífico de Matemáticas . 85 (2): 261–294. doi : 10.2140/pjm.1979.85.261 . ISSN  0030-8730.
8. Grytczuk, Jarosław (28 de mayo de 2007). "Evitación de patrones en grafos". Matemáticas discretas . Cuarta Conferencia Caracow sobre teoría de grafos. 307 (11): 1341–1346. doi : 10.1016/j.disc.2005.11.071 . ISSN  0012-365X.
9. Combinatoria de palabras: palabras de Christoffel y repeticiones en palabras. American Mathematical Soc. pág. 97. ISBN 978-0-8218-7325-0.
10. Fogg, N. Pytheas (23 de septiembre de 2002). Sustituciones en dinámica, aritmética y combinatoria. Springer Science & Business Media. pág. 104. ISBN 978-3-540-44141-0.
11. Allouche, Jean-Paul; Shallit, Jeffrey; Shallit, Profesor Jeffrey (2003-07-21). Secuencias automáticas: teoría, aplicaciones, generalizaciones. Cambridge University Press. p. 24. ISBN 978-0-521-82332-6.
12. Clark, Ronald J. (1 de abril de 2006). "La existencia de un patrón que es 5-evitable pero 4-inevitable". Revista internacional de álgebra y computación . 16 (2): 351–367. doi :10.1142/S0218196706002950. ISSN  0218-1967.

• Allouche, Jean-Paul; Shallit, Jeffrey (2003). Secuencias automáticas: teoría, aplicaciones, generalizaciones . Cambridge University Press . ISBN 978-0-521-82332-6.Zbl 1086.11015  .
• Berstel, Jean; Lauve, Aaron; Reutenauer, Christophe; Saliola, Franco V. (2009). Combinatoria de palabras. Palabras de Christoffel y repeticiones en palabras . Serie monográfica CRM. Vol. 27. Providence, RI: American Mathematical Society . ISBN. 978-0-8218-4480-9.Zbl 1161.68043  .
• Lothaire, M. (2011). Combinatoria algebraica sobre palabras . Enciclopedia de matemáticas y sus aplicaciones. Vol. 90. Con prólogo de Jean Berstel y Dominique Perrin (reimpresión de la edición de tapa dura de 2002). Cambridge University Press . ISBN 978-0-521-18071-9.Zbl 1221.68183  .
• Pytheas Fogg, N. (2002). Berthé, Valérie ; Ferenczi, Sébastien; Mauduit, Christian; Siegel, A. (eds.). Sustituciones en dinámica, aritmética y combinatoria . Lecture Notes in Mathematics. Vol. 1794. Berlín: Springer-Verlag . ISBN. 3-540-44141-7.Zbl 1014.11015  .