Secuencia automática

En matemáticas e 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 n -ésimo término de una secuencia automática a ( n ) es una funció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 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 ${\displaystyle \in }$ S y 0 en caso contrario. ^{[ 3 ] [ 4 ]}

Las secuencias automáticas pueden definirse de varias maneras, todas las cuales son equivalentes. A continuación se presentan cuatro definiciones comunes.

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 del tema y no utilizó la terminología que se encuentra en este artículo. La noción de secuencias automáticas fue estudiada posteriormente por Cobham en 1972, quien las denominó " secuencias de etiquetas uniformes ". ^{[ 7 ]}

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

Las siguientes secuencias son automáticas:

secuencia de Thue-Morse

La secuencia de Thue-Morse t ( n ) ( OEIS : A010060  ) es el punto fijo del morfismo 0 → 01, 1 → 10. Dado que el n -ésimo término de la secuencia de Thue-Morse cuenta el número de unos módulo 2 en la representación en 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.

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

• Cada secuencia automática es una palabra morfológica . ^{[ 21 ]}
• Para k  ≥  2 y r  ≥  1, una secuencia es k -automática si y solo si es k ^r -automática. Este resultado se debe a Eilenberg. ^{[ 22 ]}
• Para h y k multiplicativamente independientes , una sucesión es h -automática y k -automática si y solo si es finalmente periódica. ^{[ 23 ]} Este resultado se debe a Cobham, también conocido como el teorema de Cobham , ^{[ 24 ]} con una generalización multidimensional debida a Semenov. ^{[ 25 ] [ 26 ]}
• Si u ( n ) es una sucesión k -automática sobre un alfabeto Σ y f es un morfismo uniforme de Σ ^∗ a otro alfabeto Δ ^∗ , entonces f ( u ) es una sucesión k -automática sobre Δ. ^{[ 27 ]}
• Si u ( n ) es una secuencia k -automática, entonces las secuencias u ( kn ⁾ y u ( kn ^- 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 ( kn ⁾ = u ( n ) y cero en caso contrario es k -automática. ^{[ 29 ]} 

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

${\displaystyle t=011010011\dots }$

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

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

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

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

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

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

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

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

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

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

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

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

Las secuencias k -automáticas normalmente solo se definen para k  ≥  2. ^{[ 1 ]} El concepto puede extenderse a k = 1 definiendo una secuencia 1-automática como una secuencia cuyo n -ésimo término 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.

Las secuencias automáticas son robustas frente a variaciones tanto en la definición como en la secuencia de entrada. Por ejemplo, como se indica en la definición teórica de autómatas, una secuencia dada permanece automática tanto en lectura directa como inversa de la secuencia de entrada. Una secuencia también permanece 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 secuencia automática puede extenderse desde los números naturales hasta los enteros mediante secuencias automáticas bilaterales . Esto se debe a que, dado k  ≥  2, cada entero puede representarse de forma única en la forma${\displaystyle \sum _{0\leq i\leq r}a_{i}(-k)^{i},}$dónde${\displaystyle a_{i}\in \{0,\dots ,k-1\}}$Entonces, una secuencia infinita bilateral a ( n ) _{n ${\displaystyle \in \mathbb {Z} }$}es (− k )-automática si y solo si sus subsecuencias a ( n ) _{n ≥ 0} y a (− n ) _{n ≥ 0} son k -automáticas. ^{[ 34 ]}

El alfabeto de una secuencia k -automática puede extenderse de tamaño finito a tamaño infinito mediante secuencias k -regulares . ^{[ 35 ]} Las secuencias k -regulares se caracterizan por ser secuencias cuyo k -núcleo es finitamente generado. Toda secuencia k -regular acotada es automática. ^{[ 36 ]}

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

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

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

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

• Aritmética de Büchi

• Allouche, Jean-Paul; Shallit, Jeffrey (2003). Automatic Sequences: Theory, Applications, Generalizations . 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 de monografías 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 . 

• 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 . pp. 215–228 . ISBN  978-0-521-33545-4. Zbl 0656.10032 . 
• Rowland, Eric (2015). "¿Qué es... una secuencia automática?" . Notices of the 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 . pp. 547-570 . ISBN  978-0-387-98824-5.