En matemáticas e informática teórica , una secuencia automática (también llamada k- secuencia automática o k- secuencia reconocible cuando se quiere indicar que la base de los numerales utilizados es k ) es una secuencia infinita de términos caracterizados por un autómata finito . El n -ésimo término de una secuencia automática a ( n ) es un mapeo 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 los cuales 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]
Definición
Las secuencias automáticas se pueden definir de varias formas, todas equivalentes. Cuatro definiciones comunes son las siguientes.
Automata-teórico
Sea k un entero positivo , y sea D = ( Q , Σ k , δ, q 0 , Δ, τ) 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 0 ∈ Q es el estado inicial;
- el alfabeto de salida Δ es un conjunto finito; y
- τ: Q → Δ es el mapeo de la función de salida del conjunto de estados internos al alfabeto de salida.
Extienda la función de transición δ de actuar sobre un solo dígito a actuar sobre cadenas de dígitos definiendo la acción de δ en una cadena s que consta de dígitos s 1 s 2 ... s t como:
- δ ( q , s ) = δ (δ ( q 0 , s 1 s 2 ... s t -1 ), s t ).
Defina una función a del conjunto de números enteros positivos al alfabeto de salida Δ de la siguiente manera:
- a ( n ) = τ (δ ( q 0 , s ( n ))),
donde s ( n ) es n escrito en base k . Entonces la secuencia a = a (1) a (2) a (3) ... es una k- secuencia automática. [1]
Un autómata que lee los dígitos en base k de s ( n ) que comienzan con el dígito más significativo se dice que es lectura directa , mientras que un autómata que comienza con el dígito menos significativo es lectura inversa . [4] La definición anterior es válida si s ( n ) es lectura directa o inversa. [5]
Sustitución
Dejar be a k - morfismo uniforme de un monoide libre y deja ser una codificación (es decir, una-morfismo uniforme), como en el caso teórico-autómata. Sies un punto fijo de—Es decir, si -luego es una secuencia k- automática. [6] A la inversa, cada secuencia k- automática se puede obtener de esta manera. [4] Este resultado se debe a Cobham, y en la literatura se lo conoce como el pequeño teorema de Cobham . [2] [7]
k- kernel
Sea k ≥ 2. El k-kernel de la secuencia s ( n ) es el conjunto de subsecuencias
En la mayoría de los casos, el k- núcleo de una secuencia es infinito. Sin embargo, si el k -kernel es finito, entonces la secuencia s ( n ) es k -automática y lo contrario también es cierto. 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 poder formal
Sea u ( n ) una secuencia sobre un alfabeto Σ y suponga que hay una función inyectiva β desde Σ al campo finito F q , donde q = p n para algún primo p . La serie de poder formal asociada es
Entonces la secuencia u es q -automática si y solo si esta serie formal de potencias es algebraica sobre F q ( X ). Este resultado se debe a Christol, y en la literatura se lo denomina 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 del asunto y no utilizó la terminología que se encuentra en este artículo. La noción de secuencias automáticas fue estudiada 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 de
Las siguientes secuencias son automáticas:
Secuencia de Thue-Morse
La secuencia 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 Thue-Morse cuenta el número de unidades módulo 2 en el representación en base 2 de n , es generada por el autómata finito determinista de dos estados con la salida que se muestra aquí, donde estar en el estado q 0 indica que hay un número par de unos en la representación de n y estar en el estado q 1 indica que hay son un número impar de unos. Por lo tanto, la secuencia Thue-Morse es automática en 2.
Secuencia de duplicación de períodos
El n -ésimo término de la secuencia de duplicación del período d ( n ) ( OEIS : A096268 ) está determinado por la paridad del exponente de la potencia más alta de 2 que divide 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 uniforme 2 φ en w donde φ (0) = 01 y φ (1) = 00, es evidente que la secuencia de duplicación del período es el punto fijo de φ ( w ) y, por lo tanto, es 2-automática.
Secuencia de Rudin-Shapiro
El n -ésimo término de la secuencia de Rudin-Shapiro r ( n ) ( OEIS : A020985 ) está determinado por el número de consecutivos en la representación en base 2 de n . El 2-núcleo de la secuencia de Rudin-Shapiro [15] es
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ático.
Otras secuencias
Tanto la secuencia Baum-Sweet [16] ( OEIS : A086747 ) como la secuencia de plegado de papel normal [17] [18] [19] ( OEIS : A014577 ) son automáticas. Además, la secuencia general de plegado del papel con una secuencia periódica de plegados también es automática. [20]
Propiedades
Las secuencias automáticas exhiben una serie de propiedades interesantes. A continuación se presenta una lista no exhaustiva de estas propiedades.
- Cada secuencia automática es una palabra mórfica . [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 secuencia es h- automática y k- automática si y solo si es en última instancia periódica. [23] Este resultado se debe a Cobham, [24] con una generalización multidimensional debida a Semenov. [25] [26]
- Si u ( n ) es una k- secuencia automática sobre un alfabeto Σ yf es un morfismo uniforme de Σ ∗ a otro alfabeto Δ ∗ , entonces f ( u ) es una k- secuencia automática sobre Δ. [27]
- Si u ( n ) es una secuencia k- automática, entonces las secuencias u ( k n ) yu ( k n - 1) son finalmente periódicas. [28] A la inversa, si u ( n ) es una secuencia periódica en última instancia, entonces la secuencia v definida por v ( k n ) = u ( n ) y, en caso contrario, cero es k- automática. [29]
Probar y refutar la automaticidad
Dada una secuencia candidata , suele ser más fácil refutar su automaticidad que probarlo. Mediante la caracterización del k- núcleo de las k- secuencias automáticas, es suficiente para producir una infinidad de elementos distintos en el k- núcleo para mostrar que no es k- automático. Heurísticamente, uno podría intentar probar la automaticidad comprobando la concordancia de los términos en el k -kernel, pero esto ocasionalmente puede conducir a conjeturas erróneas. Por ejemplo, deja
sea la palabra Thue-Morse. Dejar ser la palabra dada por la concatenación de términos sucesivos en la secuencia de longitudes de ejecución de . Luego comienza
- .
Se sabe que es el punto fijo del morfismo
La palabra no es 2-automático, pero ciertos elementos de su 2-kernel están de acuerdo en muchos términos. Por ejemplo,
pero no para . [30]
Dada una secuencia que se supone 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. Dejar escrito en el alfabeto , y deja denotar la base Expansión de . Entonces la secuencia es -automático si y solo cada una de las fibras
es un idioma regular. [31] La verificación de la regularidad de las fibras a menudo se puede realizar utilizando el lema de bombeo para los idiomas regulares .
Si denota la suma de los dígitos en la base- Expansión de y es un polinomio con coeficientes enteros no negativos, y si , son enteros, entonces la secuencia
es -automático si y solo si o . [32]
1-secuencias automáticas
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) n . Dado que un autómata de estado finito debe volver eventualmente a un estado visitado previamente, todas las secuencias automáticas 1 son en última instancia periódicas.
Generalizaciones
Las secuencias automáticas son resistentes a las variaciones de la definición o de la secuencia de entrada. Por ejemplo, como se indica en la definición de la teoría de los autómatas, una secuencia determinada permanece automática tanto en la lectura directa como en la inversa de la secuencia de entrada. Una secuencia también permanece automática cuando se usa 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, en contraste con el 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 de dos caras . Esto se debe al hecho de que, dado k ≥ 2, cada número entero se puede representar de forma única en la forma dónde . Entonces una secuencia infinita de dos lados a ( n ) n es (- k ) -automático 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 desde un tamaño finito a un tamaño infinito a través de secuencias k -regulares . [35] Las secuencias k -regulares se pueden caracterizar como aquellas secuencias cuyo núcleo- k se genera de forma finita. Cada secuencia k -regular limitada es automática. [36]
Enfoque lógico
Para muchas secuencias de 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]
Por ejemplo, las siguientes propiedades de la palabra Thue-Morse pueden verificarse mecánicamente de esta manera:
- La palabra Thue-Morse no se superpone, es decir, no contiene una palabra de la forma dónde es una sola letra y es una palabra posiblemente vacía.
- Una palabra no vacía está bordeado si hay una palabra que no esté vacía y una palabra posiblemente vacía con . La palabra Thue-Morse contiene un factor de borde para cada longitud mayor que 1. [38]
- Hay un factor de longitud ilimitado en la palabra Thue-Morse si y solo si dónde denota la representación binaria de . [39]
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 de las secuencias automáticas.
Ver también
- Aritmética Büchi
Notas
- ↑ a b c Allouche y Shallit (2003) p. 152
- ↑ a b Berstel et al (2009) p. 78
- ^ Allouche y Shallit (2003) p. 168
- ↑ a b c Pytheas Fogg (2002) p. 13
- ^ Pytheas Fogg (2002) p. 15
- ^ Allouche y Shallit (2003) p. 175
- ↑ a b Cobham (1972)
- ^ Allouche y Shallit (2003) p. 185
- ^ Lothaire (2005) p. 527
- ^ Berstel y Reutenauer (2011) p. 91
- ^ Christol, G. (1979). "Ensembles presque périodiques k -reconnaissables". Theoret. Computación. Sci . 9 : 141-145. doi : 10.1016 / 0304-3975 (79) 90011-2 .
- ^ Büchi, JR (1960). Aritmética de segundo orden débil y autómatas finitos . Z. Math. Logik Grundlagen Math . 6 . págs. 66–92. doi : 10.1007 / 978-1-4613-8928-6_22 . ISBN 978-1-4613-8930-9.
- ^ Deshouillers, J.-M. (1979-1980). "La répartition modulo 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.
- ^ Allouche y Shallit (2003) p. 176
- ^ Allouche y Shallit (2003) p. 186
- ^ Allouche y Shallit (2003) p. 156
- ^ Berstel y Reutenauer (2011) p. 92
- ^ Allouche y Shallit (2003) p. 155
- ^ Lothaire (2005) p. 526
- ^ Allouche y Shallit (2003) p. 183
- ^ Lothaire (2005) p. 524
- ^ Eilenberg, Samuel (1974). Autómatas, lenguajes y máquinas . Una . Orlando: Prensa académica . ISBN 978-0-122-34001-7.
- ^ Allouche y Shallit (2003) págs. 345-350
- ^ Cobham, A. (1969). "Sobre la base-dependencia de conjuntos de números reconocibles por autómatas finitos". Matemáticas. Teoría de sistemas . 3 (2): 186-192. doi : 10.1007 / BF01746527 .
- ^ Semenov, AL (1977). "Presburgerness de predicados regulares en dos sistemas numéricos". Sibirsk. Estera. Z h. (en ruso). 18 : 403–418.
- ^ Point, F .; Bruyère, V. (1997). "Sobre el teorema de Cobham-Semenov". Teoría de los sistemas informáticos . 30 (2): 197–220. doi : 10.1007 / BF02679449 .
- ^ Lothaire (2005) p. 532
- ^ Lothaire (2005) p. 529
- ^ Berstel y Reutenauer (2011) p. 103
- ^ Allouche, G .; Allouche, J.-P .; Shallit, J. (2006). "Kolam indiens, dessins sur le sable aux îles Vanuatu, courbe de Sierpinski et morphismes de monoïde". Annales de l'Institut Fourier . 56 (7): 2126. doi : 10.5802 / aif.2235 .
- ^ Allouche y Shallit (2003) p. 160
- ^ Allouche y Shallit (2003) p. 197
- ^ Allouche y Shallit (2003) p. 157
- ^ Allouche y Shallit (2003) p. 162
- ^ Allouche, J.-P .; Shallit, J. (1992), "El anillo de k -secuencias regulares ", Theoret. Computación. Sci. , 98 (2): 163–197, doi : 10.1016 / 0304-3975 (92) 90001-v
- ^ Lo haré, Jeffrey. "El enfoque lógico de las secuencias automáticas, parte 1: secuencias automáticas y k -secuencias regulares" (PDF) . Consultado el 1 de abril de 2020 .
- ^ Shallit, J. "El enfoque lógico de las secuencias automáticas: Parte 1" (PDF) . Consultado el 1 de abril de 2020 .
- ^ Shallit, J. "El enfoque lógico de las secuencias automáticas: Parte 3" (PDF) . Consultado el 1 de abril de 2020 .
- ^ Shallit, J. "El enfoque lógico de las secuencias automáticas: Parte 3" (PDF) . Consultado el 1 de abril de 2020 .
- ^ Shallit, J. "Walnut Software" . Consultado el 1 de abril de 2020 .
- ^ Mousavi, H. (2016). "Demostración automática de teoremas en nuez". arXiv : 1603.06017 [ cs.FL ].
Referencias
- Allouche, Jean-Paul; Shallit, Jeffrey (2003). Secuencias automáticas: teoría, aplicaciones, generalizaciones . Prensa de la Universidad de Cambridge . ISBN 978-0-521-82332-6. Zbl 1086.11015 .
- Berstel, Jean; Lauve, Aaron; Reutenauer, Christophe; Saliola, Franco V. (2009). Combinatoria de palabras. Christoffel palabras y repeticiones en palabras . Serie de monografías CRM. 27 . Providence, RI: Sociedad Matemática Estadounidense . ISBN 978-0-8218-4480-9. Zbl 1161.68043 .
- Berstel, Jean; Reutenauer, Christophe (2011). Serie racional no conmutativa con aplicaciones . Enciclopedia de las matemáticas y sus aplicaciones. 137 . Cambridge: Cambridge University Press . ISBN 978-0-521-19022-0. Zbl 1250.68007 .
- Cobham, Alan (1972). "Secuencias de etiquetas uniformes". Matemáticas. Teoría de sistemas . 6 (1–2): 164–192. doi : 10.1007 / BF01706087 .
- Lothaire, M. (2005). Combinatoria aplicada sobre palabras . Enciclopedia de las matemáticas y sus aplicaciones. 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: Cambridge University Press . ISBN 978-0-521-84802-2. Zbl 1133.68067 .
- Pytheas Fogg, N. (2002). Sustituciones en dinámica, aritmética y combinatoria . Apuntes de clase en matemáticas. 1794 . Editores Berthé, Valérie ; Ferenczi, Sébastien; Mauduit, Christian; Siegel, A. Berlín: Springer-Verlag . ISBN 978-3-540-44141-0. Zbl 1014.11015 .
Otras lecturas
- Berthé, Valérie; Rigo, Michel, eds. (2010). Combinatoria, autómatas y teoría de números . Enciclopedia de Matemáticas y sus Aplicaciones. 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 . Prensa de la Universidad de Cambridge . 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 de IMA, Minneapolis, MN, EE. UU., 15 al 26 de julio de 1996 . Los volúmenes IMA en matemáticas y sus aplicaciones. 109 . Springer-Verlag . págs. 547–570. ISBN 978-0-387-98824-5.