En matemáticas y ciencias de la computación teóricas , una secuencia k -regular es una secuencia que satisface ecuaciones de recurrencia lineal que reflejan las representaciones en base- k de los enteros. La clase de k- secuencias regulares generaliza la clase de k- secuencias automáticas a alfabetos de tamaño infinito.
Definición
Existen varias caracterizaciones de k- secuencias regulares, todas las cuales son equivalentes. Algunas caracterizaciones comunes son las siguientes. Para cada uno, tomamos R ′ como un anillo conmutativo Noetheriano y tomamos R como un anillo que contiene R ′.
k- kernel
Sea k ≥ 2. El k-kernel de la secuencia es el conjunto de subsecuencias
La secuencia es ( R ′, k ) -regular (a menudo abreviado a solo " k -regular") si el-module generada por K k ( s ) es un tipo finito- R '- módulo . [1]
En el caso especial cuando , la secuencia es -regular si está contenido en un espacio vectorial de dimensión finita sobre .
Combinaciones lineales
Una secuencia s ( n ) es k -regular si existe un entero E tal que, para todo e j > E y 0 ≤ r j ≤ k e j - 1, cada subsecuencia de s de la forma s ( k e j n + r j ) es expresable como una R ′ - combinación lineal , donde c ij es un número entero, f ij ≤ E , y 0 ≤ b ij ≤ k f ij - 1. [2]
Alternativamente, una secuencia s ( n ) es k -regular si existe un entero r y subsecuencias s 1 ( n ), ..., s r ( n ) tales que, para todo 1 ≤ i ≤ r y 0 ≤ a ≤ k - 1, cada secuencia s i ( kn + a ) en el k -núcleo K k ( s ) es una combinación lineal R 'de las subsecuencias s i ( n ). [2]
Serie formal
Sea x 0 , ..., x k - 1 un conjunto de k variables no conmutadas y sea τ un mapa que envía un número natural n a la cadena x a 0 ... x a e - 1 , donde la base - k representación de x es la cadena a e - 1 ... a 0 . Entonces una secuencia s ( n ) es k -regular si y solo si la serie formal es - racional . [3]
Automata-teórico
La definición formal en serie de una secuencia k -regular conduce a una caracterización de autómata similar a la máquina matricial de Schützenberger . [4] [5]
Historia
La noción de secuencias k -regulares fue investigada por primera vez en un par de artículos de Allouche y Shallit. [6] Antes de esto, Berstel y Reutenauer estudiaron la teoría de las series racionales , que está estrechamente relacionada con las secuencias k -regulares. [7]
Ejemplos de
Secuencia de la regla
Dejar ser el -valuación ádica de. La secuencia de la regla( OEIS : A007814 ) es-regular, y el -núcleo
está contenido en el espacio vectorial bidimensional generado por y la secuencia constante . Estos elementos básicos conducen a las relaciones de recurrencia.
que, junto con las condiciones iniciales y , determina de forma única la secuencia. [8]
Secuencia de Thue-Morse
La secuencia Thue-Morse t ( n ) ( OEIS : A010060 ) es el punto fijo del morfismo 0 → 01, 1 → 10. Se sabe que la secuencia Thue-Morse es 2-automática. Por lo tanto, también es 2-regular, y su 2-kernel
consta de las subsecuencias y .
Números de Cantor
La secuencia de números de Cantor c ( n ) ( OEIS : A005823 ) consta de números cuyas expansiones ternarias no contienen 1. Es sencillo demostrar que
y por lo tanto la secuencia de números de Cantor es 2-regular. De manera similar, la secuencia de Stanley
de números cuyas expansiones ternarias no contienen 2 también es 2-regular. [9]
Ordenar números
Una aplicación algo interesante de la noción de k -regularidad al estudio más amplio de algoritmos se encuentra en el análisis del algoritmo de clasificación por fusión . Dada una lista de n valores, el número de comparaciones realizadas por el algoritmo de clasificación por fusión son los números de clasificación , regidos por la relación de recurrencia
Como resultado, la secuencia definida por la relación de recurrencia para la ordenación por fusión, T ( n ), constituye una secuencia regular 2. [10]
Otras secuencias
Si es un polinomio de valores enteros , entonceses k -regular para cada.
La secuencia Glaisher-Gould es 2-regular. La secuencia de Stern-Brocot es 2-regular.
Allouche y Shallit dan varios ejemplos adicionales de secuencias k -regulares en sus artículos. [6]
Propiedades
Las secuencias k -regulares exhiben una serie de propiedades interesantes.
- Cada k- secuencia automática es k -regular. [11]
- Cada secuencia k- sincronizada es k -regular.
- Una secuencia k -regular toma un número finito de valores si y solo si es k -automática. [12] Esto es una consecuencia inmediata de que la clase de k- secuencias regulares es una generalización de la clase de k- secuencias automáticas.
- La clase de secuencias k -regulares se cierra bajo suma de términos, multiplicación de términos y convolución . La clase de k- secuencias regulares también se cierra escalando cada término de la secuencia por un entero λ. [12] [13] [14] [15] En particular, el conjunto de k -series de potencias regulares forma un anillo. [dieciséis]
- Si es k -regular, entonces para todos los enteros, es k -automático. Sin embargo, lo contrario no se sostiene. [17]
- Para k , l ≥ 2 multiplicativamente independiente , si una secuencia es tanto k -regular como l -regular, entonces la secuencia satisface una recurrencia lineal. [18] Esta es una generalización de un resultado de Cobham con respecto a secuencias que son tanto k- automáticas como l- automáticas. [19]
- El n º plazo de un k secuencia -regular de enteros crece a más polinomialmente en n . [20]
- Si es un campo y , luego la secuencia de poderes es k -regular si y solo si o es una raíz de unidad. [21]
Probar y refutar la regularidad k
Dada una secuencia candidata que no se sabe que sea k -regular, k -regularidad típicamente se puede probar directamente a partir de la definición mediante el cálculo de elementos del kernel de y demostrando que todos los elementos del formulario con suficientemente grande y pueden escribirse como combinaciones lineales de elementos del núcleo con exponentes más pequeños en lugar de . Esto suele ser computacionalmente sencillo.
Por otro lado, refutar k -regularidad de la secuencia candidata generalmente requiere uno para producir un -subconjunto linealmente independiente en el núcleo de , que suele ser más complicado. Aquí hay un ejemplo de tal prueba.
Dejar denotar el número de está en la expansión binaria de . Dejar denotar el número de está en la expansión binaria de . La secuenciase puede demostrar que es 2-regular. La secuenciaes, sin embargo, no 2-regular, por el siguiente argumento. Suponeres 2-regular. Afirmamos que los elementos por y del 2-kernel de son linealmente independientes sobre . La función es sobreyectiva sobre los enteros, así que deja ser el menor número entero tal que . Por 2-regularidad de, allí existe y constantes tal que para cada ,
Dejar ser el menor valor por el cual . Entonces para cada,
Evaluando esta expresión en , dónde y así sucesivamente, obtenemos, en el lado izquierdo
y en el lado derecho,
De ello se deduce que para cada entero ,
Pero para , el lado derecho de la ecuación es monótono porque tiene la forma para algunas constantes , mientras que el lado izquierdo no lo es, como se puede comprobar conectando sucesivamente , , y . Por lo tanto,no es 2-regular. [22]
Notas
- ^ Allouche y Shallit (1992), definición 2.1.
- ↑ a b Allouche y Shallit (1992), Teorema 2.2.
- ^ Allouche y Shallit (1992), Teorema 4.3.
- ^ Allouche y Shallit (1992), Teorema 4.4.
- ↑ Schützenberger, M.-P. (1961), "Sobre la definición de una familia de autómatas", Información y control , 4 (2-3): 245-270, doi : 10.1016 / S0019-9958 (61) 80020-X.
- ↑ a b Allouche y Shallit (1992, 2003).
- ^ Berstel, Jean; Reutenauer, Christophe (1988). Series racionales y sus lenguajes . Monografías de la EATCS sobre informática teórica. 12 . Springer-Verlag . ISBN 978-3-642-73237-9.
- ^ Allouche y Shallit (1992), ejemplo 8.
- ^ Allouche y Shallit (1992), Ejemplos 3 y 26.
- ^ Allouche y Shallit (1992), ejemplo 28.
- ^ Allouche y Shallit (1992), Teorema 2.3.
- ↑ a b Allouche y Shallit (2003) p. 441.
- ^ Allouche y Shallit (1992), Teorema 2.5.
- ^ Allouche y Shallit (1992), Teorema 3.1.
- ^ Allouche y Shallit (2003) p. 445.
- ^ Allouche y Shallit (2003) p. 446.
- ^ Allouche y Shallit (2003) p. 441.
- ^ Bell, J. (2006). "Una generalización del teorema de Cobham para secuencias regulares". Séminaire Lotharingien de Combinatoire . 54A .
- ^ 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 .
- ^ Allouche y Shallit (1992) Teorema 2.10.
- ^ Allouche y Shallit (2003) p. 444.
- ^ Allouche y Shallit (1993) p. 168-169.
Referencias
- Allouche, Jean-Paul; Shallit, Jeffrey (1992), "El anillo de k -secuencias regulares ", Theoret. Computación. Sci. , 98 (2): 163–197, doi : 10.1016 / 0304-3975 (92) 90001-v.
- Allouche, Jean-Paul; Shallit, Jeffrey (2003), "El anillo de k -secuencias regulares , II", Theoret. Computación. Sci. , 307 : 3–29, doi : 10.1016 / s0304-3975 (03) 00090-2.
- 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 .