Secuencia automática

Secuencia infinita de términos caracterizada por un autómata finito

En matemáticas y en informática teórica , una secuencia automática (también llamada secuencia k -automática o secuencia k -reconocible cuando se quiere indicar que la base de los numerales utilizados es k ) es una secuencia infinita de términos caracterizada por un autómata finito . El término n -ésimo de una secuencia automática a ( n ) es una aplicación del estado final alcanzado en un autómata finito que acepta los dígitos del número n en alguna base  fija k . ^{[1] [2]}

Un conjunto automático es un conjunto de números enteros no negativos S para el cual la secuencia de valores de su función característica χ _S es una secuencia automática; es decir, S es k -automático si χ _S ( n ) es k -automático, donde χ _S ( n ) = 1 si n  S y 0 en caso contrario. ^{[3] [4]} ${\displaystyle \in }$ 

Definición

Las secuencias automáticas pueden definirse de varias maneras, todas ellas equivalentes. A continuación se indican cuatro definiciones comunes:

Teoría de autómatas

Sea k un entero positivo y sea D = ( Q , Σ _k , δ, q ₀ , Δ, τ) un autómata finito determinista con salida , donde

• Q es el conjunto finito de estados;
• El alfabeto de entrada Σ _k consiste en el conjunto {0,1,..., k -1} de dígitos posibles en notación base - k ;
• δ : Q × Σ _k → Q es la función de transición;
• q ₀ ∈ Q es el estado inicial;
• el alfabeto de salida Δ es un conjunto finito; y
• τ : Q → Δ es la función de salida que asigna el conjunto de estados internos al alfabeto de salida.

Amplíe la función de transición δ de actuar sobre dígitos individuales a actuar sobre cadenas de dígitos definiendo la acción de δ sobre una cadena s que consta de dígitos s ₁ s ₂ ... s _t como:

δ( q , s ) = δ(δ( q , s ₁ s ₂ ... s _{t -1} ), s _t ).

Defina una función a del conjunto de números enteros positivos con el alfabeto de salida Δ de la siguiente manera:

a ( norte ) = τ(δ( q ₀ , s ( norte ))),

donde s ( n ) es n escrito en base k . Entonces la secuencia a = a (1) a (2) a (3)... es una secuencia k -automática. ^[1]

Se dice que un autómata que lee los dígitos base k de s ( n ) comenzando con el dígito más significativo es de lectura directa , mientras que un autómata que comienza con el dígito menos significativo es de lectura inversa . ^[4] La definición anterior es válida independientemente de si s ( n ) es de lectura directa o inversa. ^[5]

Sustitución

Sea un morfismo k - uniforme de un monoide libre y sea una codificación (es decir, un morfismo -uniforme), como en el caso de la teoría de autómatas. Si es un punto fijo de —es decir, si —entonces es una secuencia k -automática. ^[6] A la inversa, toda secuencia k -automática se puede obtener de esta manera. ^[4] Este resultado se debe a Cobham y se lo conoce en la literatura como el pequeño teorema de Cobham . ^{[2] [7]} ${\displaystyle \varphi }$ ${\displaystyle \Sigma ^{*}}$ ${\displaystyle \tau }$ ${\displaystyle 1}$ ${\displaystyle w}$ ${\displaystyle \varphi }$ ${\displaystyle w=\varphi (w)}$ ${\displaystyle s=\tau (w)}$

a-núcleo

Sea k  ≥ 2. El k-núcleo de la secuencia s ( n ) es el conjunto de subsecuencias

${\displaystyle K_{k}(s)=\{s(k^{e}n+r):e\geq 0{\text{ and }}0\leq r\leq k^{e}-1\}.}$

En la mayoría de los casos, el k -núcleo de una secuencia es infinito. Sin embargo, si el k -núcleo es finito, entonces la secuencia s ( n ) es k -automática, y la inversa también es cierta. Esto se debe a Eilenberg. ^{[8] [9] [10]}

De ello se deduce que una secuencia k -automática es necesariamente una secuencia en un alfabeto finito.

Serie de potencias formales

Sea u ( n ) una secuencia sobre un alfabeto Σ y supongamos que existe una función inyectiva β desde Σ hasta el cuerpo finito F _q , donde q = p ⁿ para algún primo p . La serie de potencias formal asociada es

${\displaystyle \sum _{i\geq 0}\beta (u(i))X^{i}.}$

Entonces la secuencia u es q -automática si y sólo si esta serie de potencias formal es algebraica sobre F _q ( X ). Este resultado se debe a Christol, y en la literatura se lo conoce como el teorema de Christol . ^[11]

Historia

Las secuencias automáticas fueron introducidas por Büchi en 1960, ^[12] aunque su artículo adoptó un enfoque más lógico-teórico y no utilizó la terminología que se encuentra en este artículo. El concepto de secuencias automáticas fue estudiado más a fondo por Cobham en 1972, quien llamó a estas secuencias " secuencias de etiquetas uniformes ". ^[7]

El término "secuencia automática" apareció por primera vez en un artículo de Deshouillers. ^[13]

Ejemplos

Las siguientes secuencias son automáticas:

Secuencia Thue-Morse

DFAO generando la secuencia Thue-Morse

La secuencia de Thue-Morse t ( n ) ( OEIS : A010060 ) es el punto fijo del morfismo 0 → 01, 1 → 10. Dado que el término n -ésimo de la secuencia de Thue-Morse cuenta el número de unos módulo 2 en la representación de base 2 de n , se genera mediante el autómata finito determinista de dos estados con la salida que se muestra aquí, donde estar en el estado q ₀ indica que hay un número par de unos en la representación de n y estar en el estado q ₁ indica que hay un número impar de unos. Por lo tanto, la secuencia de Thue-Morse es 2-automática.

Secuencia de duplicación de período

El término n -ésimo de la secuencia de duplicación de período d ( n ) ( OEIS : A096268 ) está determinado por la paridad del exponente de la potencia más alta de 2 que divide a n . También es el punto fijo del morfismo 0 → 01, 1 → 00. ^[14] Comenzando con el término inicial w = 0 e iterando el morfismo 2-uniforme φ en w donde φ(0) = 01 y φ(1) = 00, es evidente que la secuencia de duplicación de período es el punto fijo de φ( w ) y, por lo tanto, es 2-automática.

Secuencia de Rudin-Shapiro

El término n -ésimo de la secuencia de Rudin–Shapiro r ( n ) ( OEIS : A020985 ) está determinado por el número de unos consecutivos en la representación en base 2 de n . El núcleo 2 de la secuencia de Rudin–Shapiro ^[15] es

${\displaystyle {\begin{aligned}r(2n)&=r(n),\\r(4n+1)&=r(n),\\r(8n+7)&=r(2n+1),\\r(16n+3)&=r(8n+3),\\r(16n+11)&=r(4n+3).\end{aligned}}}$

Dado que el núcleo 2 consta solo de r ( n ), r (2 n  + 1), r (4 n  + 3) y r (8 n  + 3), es finito y, por lo tanto, la secuencia de Rudin–Shapiro es 2-automática.

Otras secuencias

Tanto la secuencia Baum–Sweet ^[16] ( OEIS : A086747 ) como la secuencia de plegado de papel regular ^{[17] [18] [19]} ( OEIS : A014577 ) son automáticas. Además, la secuencia de plegado de papel general con una secuencia periódica de pliegues también es automática. ^[20]

Propiedades

Las secuencias automáticas presentan una serie de propiedades interesantes. A continuación se presenta una lista no exhaustiva de dichas propiedades.

• Toda secuencia automática es una palabra mórfica . ^[21]
• Para k  ≥ 2 y r  ≥ 1, una secuencia es k -automática si y sólo si es k ^r -automática. Este resultado se debe a Eilenberg. ^[22]
• Para h y k multiplicativamente independientes , una secuencia es a la vez h -automática y k -automática si y solo si es en última instancia periódica. ^[23] Este resultado se debe a Cobham, también conocido como teorema de Cobham , ^[24] con una generalización multidimensional debida a Semenov. ^{[25] [26]}
• Si u ( n ) es una secuencia k -automática sobre un alfabeto Σ y f es un morfismo uniforme de Σ ^∗ a otro alfabeto Δ ^∗ , entonces f ( u ) es una secuencia k -automática sobre Δ. ^[27]
• Si u ( n ) es una secuencia k -automática, entonces las secuencias u ( k ⁿ ) y u ( k ⁿ  − 1) son en última instancia periódicas. ^[28] Por el contrario, si u ( n ) es una secuencia en última instancia periódica, entonces la secuencia v definida por v ( k ⁿ ) = u ( n ) y en caso contrario cero es k -automática. ^[29]

Demostrando y refutando la automaticidad

Dada una secuencia candidata , suele ser más fácil refutar su automaticidad que probarla. Mediante la caracterización de k -kernel de secuencias k -automáticas, basta con producir una cantidad infinita de elementos distintos en el k -kernel para demostrar que no es k -automática. Heurísticamente, se podría intentar probar la automaticidad comprobando la concordancia de términos en el k -kernel, pero esto puede conducir ocasionalmente a suposiciones erróneas. Por ejemplo, sea ${\displaystyle s=(s_{n})_{n\geq 0}}$ ${\displaystyle K_{k}(s)}$ ${\displaystyle s}$

${\displaystyle t=011010011\dots }$

sea ​​la palabra Thue-Morse. Sea la palabra obtenida al concatenar términos sucesivos en la secuencia de longitudes de ejecución de . Entonces comienza ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle s}$

${\displaystyle s=12112221\dots .}$.

Se sabe que es el punto fijo del morfismo. ${\displaystyle s}$ ${\displaystyle h^{\omega }(1)}$

${\displaystyle h(1)=121,h(2)=12221.}$

La palabra no es 2-automática, pero ciertos elementos de su núcleo 2 concuerdan para muchos términos. Por ejemplo, ${\displaystyle s}$ ${\displaystyle s_{16n+1}=s_{64n+1}{\text{ for }}0\leq n\leq 1864134}$

pero no para . ^[30] ${\displaystyle n=1864135}$

Dada una secuencia que se supone que es automática, existen algunos enfoques útiles para demostrar que realmente lo es. Un enfoque es construir directamente un autómata determinista con una salida que proporcione la secuencia. Sea escrito en el alfabeto , y sea denotado el desarrollo de base de . Entonces la secuencia es -automática si y solo cada una de las fibras ${\displaystyle (s_{n})_{n\geq 0}}$ ${\displaystyle \Delta }$ ${\displaystyle (n)_{k}}$ ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle s=(s_{n})_{n\geq 0}}$ ${\displaystyle k}$

${\displaystyle I_{k}(s,d):=\{(n)_{k}\mid s_{n}=d\}}$

es un lenguaje regular. ^[31] La verificación de la regularidad de las fibras a menudo se puede realizar utilizando el lema de bombeo para lenguajes regulares .

Si denota la suma de los dígitos en la expansión base de y es un polinomio con coeficientes enteros no negativos, y si , son números enteros, entonces la secuencia ${\displaystyle s_{k}(n)}$ ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle p(X)}$ ${\displaystyle k\geq 2}$ ${\displaystyle m\geq 1}$

${\displaystyle (s_{k}(p(n)){\pmod {m}})_{n\geq 0}}$

es -automático si y sólo si o . ^[32] ${\displaystyle k}$ ${\displaystyle \deg p\leq 1}$ ${\displaystyle m\mid k-1}$

1-secuencias automáticas

Las secuencias k -automáticas normalmente solo se definen para k  ≥ 2. ^[1] El concepto se puede extender a k = 1 definiendo una secuencia 1-automática como una secuencia cuyo término n -ésimo depende de la notación unaria para n ; es decir, (1) ⁿ . Dado que un autómata de estados finitos debe eventualmente regresar a un estado visitado previamente, todas las secuencias 1-automáticas son en última instancia periódicas.

Generalizaciones

Las secuencias automáticas son robustas frente a variaciones tanto de la definición como de la secuencia de entrada. Por ejemplo, como se señala en la definición de la teoría de autómatas, una secuencia dada sigue siendo automática tanto bajo la lectura directa como inversa de la secuencia de entrada. Una secuencia también sigue siendo automática cuando se utiliza un conjunto alternativo de dígitos o cuando se niega la base; es decir, cuando la secuencia de entrada se representa en base − k en lugar de en base k . ^[33] Sin embargo, a diferencia del uso de un conjunto alternativo de dígitos, un cambio de base puede afectar la automaticidad de una secuencia.

El dominio de una sucesión automática puede extenderse desde los números naturales a los enteros mediante sucesiones automáticas bilaterales . Esto se debe al hecho de que, dado k  ≥ 2, cada entero puede representarse de forma única en la forma donde . Entonces, una sucesión infinita bilateral a ( n ) _n es (− k )-automática si y solo si sus subsecuencias a ( n ) _{n ≥ 0} y a (− n ) _{n ≥ 0} son k -automáticas. ^[34] ${\displaystyle \sum _{0\leq i\leq r}a_{i}(-k)^{i},}$ ${\displaystyle a_{i}\in \{0,\dots ,k-1\}}$  _{${\displaystyle \in \mathbb {Z} }$}

El alfabeto de una secuencia k -automática se puede extender desde un tamaño finito a un tamaño infinito mediante secuencias k -regulares . ^[35] Las secuencias k -regulares se pueden caracterizar como aquellas secuencias cuyo núcleo k se genera de forma finita. Toda secuencia k -regular acotada es automática. ^[36]

Enfoque lógico

Para muchas secuencias 2-automáticas , el mapa tiene la propiedad de que la teoría de primer orden es decidible . Dado que muchas propiedades no triviales de las secuencias automáticas se pueden escribir en lógica de primer orden, es posible probar estas propiedades mecánicamente ejecutando el procedimiento de decisión. ^[37] ${\displaystyle s=(s_{n})_{n\geq 0}}$ ${\displaystyle n\mapsto s_{n}}$ ${\displaystyle {\text{FO}}(\mathbb {N} ,+,0,1,n\mapsto s_{n})}$

Por ejemplo, las siguientes propiedades de la palabra Thue-Morse se pueden verificar mecánicamente de esta manera:

• La palabra Thue-Morse no tiene superposición, es decir, no contiene ninguna palabra con la forma donde es una sola letra y es una palabra posiblemente vacía. ${\displaystyle cxcxc}$ ${\displaystyle c}$ ${\displaystyle w}$
• Una palabra no vacía está delimitada si hay una palabra no vacía y una palabra posiblemente vacía con . La palabra Thue-Morse contiene un factor delimitado para cada longitud mayor que 1. ^[38] ${\displaystyle x}$ ${\displaystyle w}$ ${\displaystyle y}$ ${\displaystyle x=wyw}$
• Hay un factor de longitud sin borde en la palabra Thue-Morse si y solo si donde denota la representación binaria de . ^[39] ${\displaystyle n}$ ${\displaystyle (n)_{2}\notin 1(01^{*}0)^{*}10^{*}1}$ ${\displaystyle (n)_{2}}$ ${\displaystyle n}$

El software Walnut, ^{[40] [41]} desarrollado por Hamoon Mousavi, implementa un procedimiento de decisión para decidir muchas propiedades de ciertas palabras automáticas, como la palabra Thue-Morse. Esta implementación es una consecuencia del trabajo anterior sobre el enfoque lógico para secuencias automáticas.

Véase también

• Aritmética de Büchi

Notas

1. Allouche y Shallit (2003) pág. 152
2. Berstel et al (2009) p. 78
3. Allouche y Shallit (2003) pág. 168
4. Pytheas Fogg (2002) pág. 13
5. Pytheas Fogg (2002) pág. 15
6. Allouche y Shallit (2003) pág. 175
7. Cobham (1972)
8. Allouche y Shallit (2003) pág. 185
9. Lothaire (2005) pág. 527
10. Berstel y Reutenauer (2011) pág. 91
11. Christol, G. (1979). "Conjuntos presque périodiques k-reconnaissables". Teoría. Computadora. Ciencia . 9 : 141-145. doi : 10.1016/0304-3975(79)90011-2 .
12. Büchi, JR (1990). "Aritmética débil de segundo orden y autómatas finitos". Obras completas de J. Richard Büchi . Z. Math. Logik Grundlagen Math. Vol. 6. págs. 66–92. doi :10.1007/978-1-4613-8928-6_22. ISBN 978-1-4613-8930-9.
13. Deshouillers, J.-M. (1979-1980). "La répartition módulo 1 des puissances de rationnels dans l'anneau des séries formelles sur un corps fini". Séminaire de Théorie des Nombres de Bordeaux : 5.01–5.22.
14. Allouche y Shallit (2003) pág. 176
15. Allouche y Shallit (2003) pág. 186
16. Allouche y Shallit (2003) pág. 156
17. Berstel y Reutenauer (2011) pág. 92
18. Allouche y Shallit (2003) pág. 155
19. Lothaire (2005) pág. 526
20. Allouche y Shallit (2003) pág. 183
21. Lothaire (2005) pág. 524
22. Eilenberg, Samuel (1974). Autómatas, lenguajes y máquinas . Vol. A. Orlando: Academic Press . ISBN. 978-0-122-34001-7.
23. Allouche y Shallit (2003) págs. 345–350
24. Cobham, A. (1969). "Sobre la dependencia de bases de conjuntos de números reconocibles por autómatas finitos". Matemáticas. Teoría de sistemas . 3 (2): 186–192. doi :10.1007/BF01746527. S2CID  19792434.
25. Semenov, AL (1977). "Presburgerness of predicates regular in two number systems" (Presburgeridad de predicados regulares en dos sistemas numéricos). Sibirsk. Mat. Zh. (en ruso). 18 (2): 403–418. Código Bibliográfico :1977SibMJ..18..289S. doi :10.1007/BF00967164.
26. Point, F.; Bruyère, V. (1997). "Sobre el teorema de Cobham-Semenov". Teoría de sistemas informáticos . 30 (2): 197–220. doi :10.1007/BF02679449. S2CID  31270341.
27. Lothaire (2005) pág. 532
28. Lothaire (2005) pág. 529
29. Berstel y Reutenauer (2011) pág. 103
30. Allouche, G.; Allouche, J.-P.; Shalit, J. (2006). "Kolam indiens, dessins sur le sable aux îles Vanuatu, courbe de Sierpinski et morphismes de monoïde". Anales del Instituto Fourier . 56 (7): 2126. doi : 10.5802/aif.2235.
31. Allouche y Shallit (2003) pág. 160
32. Allouche y Shallit (2003) pág. 197
33. Allouche y Shallit (2003) pág. 157
34. Allouche y Shallit (2003) pág. 162
35. Allouche, J.-P.; Shallit, J. (1992). "El anillo de secuencias k-regulares". Theoret. Comput. Sci . 98 (2): 163–197. doi : 10.1016/0304-3975(92)90001-v .
36. Shallit, Jeffrey. "El enfoque lógico de las secuencias automáticas, parte 1: secuencias automáticas y secuencias k-regulares" (PDF) . Consultado el 1 de abril de 2020 .
37. Shallit, J. "El enfoque lógico de las secuencias automáticas: Parte 1" (PDF) . Consultado el 1 de abril de 2020 .
38. Shallit, J. "El enfoque lógico de las secuencias automáticas: Parte 3" (PDF) . Consultado el 1 de abril de 2020 .
39. Shallit, J. "El enfoque lógico de las secuencias automáticas: Parte 3" (PDF) . Consultado el 1 de abril de 2020 .
40. Shallit, J. "Software de nuez" . Consultado el 1 de abril de 2020 .
41. Mousavi, H. (2016). "Demostración automática de teoremas en Walnut". arXiv : 1603.06017 [cs.FL].

Referencias

• 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  .
• Berstel, Jean; Reutenauer, Christophe (2011). Series racionales no conmutativas con aplicaciones . Enciclopedia de matemáticas y sus aplicaciones. Vol. 137. Cambridge: Cambridge University Press . ISBN 978-0-521-19022-0.Zbl 1250.68007  .
• Cobham, Alan (1972). "Secuencias de etiquetas uniformes". Teoría de sistemas matemáticos . 6 (1–2): 164–192. doi :10.1007/BF01706087. S2CID  28356747.
• Lotario, M. (2005). Combinatoria aplicada a las palabras . Enciclopedia de Matemáticas y sus aplicaciones. vol. 105. Una obra colectiva de Jean Berstel, Dominique Perrin, Maxime Crochemore, Eric Laporte, Mehryar Mohri, Nadia Pisanti, Marie-France Sagot, Gesine Reinert , Sophie Schbath , Michael Waterman, Philippe Jacquet, Wojciech Szpankowski , Dominique Poulalhon, Gilles Schaeffer, Roman Kolpakov, Gregory Koucherov, Jean-Paul Allouche y Valérie Berthé . Cambridge: Prensa de la Universidad de Cambridge . ISBN 978-0-521-84802-2.Zbl 1133.68067  .
• Pytheas Fogg, N. (2002). Sustituciones en dinámica, aritmética y combinatoria . Apuntes de conferencias de matemáticas. vol. 1794. Editores Berthé, Valérie ; Ferenczi, Sébastien; Mauduit, cristiano; Siegel, A. Berlín: Springer-Verlag . ISBN 978-3-540-44141-0.Zbl 1014.11015  .

Lectura adicional

• Berthé, Valérie; Rigo, Michel, eds. (2010). Combinatoria, autómatas y teoría de números . Enciclopedia de matemáticas y sus aplicaciones. Vol. 135. Cambridge: Cambridge University Press . ISBN. 978-0-521-51597-9.Zbl 1197.68006  .
• Loxton, JH (1988). "13. Autómatas y trascendencia". En Baker, A. (ed.). Nuevos avances en la teoría de la trascendencia . Cambridge University Press . págs. 215–228. ISBN 978-0-521-33545-4.Zbl 0656.10032  .
• Rowland, Eric (2015). "¿Qué es... una secuencia automática?". Avisos de la American Mathematical Society . 62 (3): 274–276. doi : 10.1090/noti1218 .
• Shallit, Jeffrey (1999). "Teoría de números y lenguajes formales". En Hejhal, Dennis A. ; Friedman, Joel; Gutzwiller, Martin C. ; Odlyzko, Andrew M. (eds.). Aplicaciones emergentes de la teoría de números. Basado en las actas del programa de verano del IMA, Minneapolis, MN, EE. UU., 15-26 de julio de 1996. Los volúmenes del IMA en matemáticas y sus aplicaciones. Vol. 109. Springer-Verlag . págs. 547-570. ISBN 978-0-387-98824-5.