Asintóticas del número de palabras en un idioma regular de longitud dada

28

Para un lenguaje regular , deje que sea ​​el número de palabras en de longitud . Usando la forma canónica de Jordan (aplicada a la matriz de transición sin anotaciones de algunos DFA para L ), se puede demostrar que para n suficientemente grande , c_n (L) = \ sum_ {i = 1} ^ k P_i (n) \ lambda_i ^ n, donde P_i son polinomios complejos y \ lambda_i son "valores propios" complejos. (Para los pequeños n , podemos tener términos adicionales de la forma C_K [n = k] , donde [n = k] es 1 si n = k y 0c n ( L ) L n L n c n ( L ) = k i = 1 P i ( n ) λ n i , P i λ i n C k [ n = k ] [ n = k ] 1 n = k 0Lcn(L)LnLn

donorte(L)=yo=1kPAGSyo(norte)λyonorte,
PAGSyoλyonortedok[norte=k][norte=k]1n=k0de otra manera. Estos corresponden a bloques de Jordan de tamaño al menos k+1 con valor propio 0 ).

Esta representación parece implicar que si L es infinito, entonces asintóticamente, cn(L)Cnkλn para algunos C,λ>0 . Sin embargo, esto es evidentemente falso: para el lenguaje L sobre {0,1} de todas las palabras de longitud par, c2n(L)=22n pero c2n+1(L)=0 . Esto sugiere que para algunos d y para todos a{0,,d1} , cdm+a(L)=0 para suficientemente grande m o cdm+aCa(dm+a)kaλadm+a . Esto se demuestra en Flajolet y Sedgewick (Teorema V.3), que atribuyen la prueba a Berstel.

La prueba proporcionada por Flajolet y Sedgewick es algo técnica; tan técnico, de hecho, que solo lo bosquejan. Intenté una prueba más elemental usando la teoría de Perron-Frobenius. Podemos considerar el gráfico de transición del DFA como un dígrafo. Si el dígrafo es primitivo, el resultado se deriva casi directamente del teorema de Perron-Frobenius. Si el dígrafo es irreducible pero imprimitive con el índice r , a continuación, considerando el " r ésima potencia" de la DFA (cada transición corresponde a r símbolos), obtenemos el mismo resultado. El caso difícil es cuando el dígrafo es reducible. Podemos reducir al caso de una ruta de componentes fuertemente conectados, y luego obtenemos el resultado estimando sumas de la forma

m1++mk=mi=1kλimi.
(Cada una de estas sumas corresponde a una forma particular de aceptar una palabra, pasando por los diferentes componentes de una manera determinada). Esta suma, a su vez, puede estimarse señalando el término más grande, que corresponde a milogλi . Por cada valor propio que se repite r veces, obtenemos un factor adicional de Θ(mr1) .

La prueba tiene sus bordes ásperos: en el caso reducible, necesitamos pasar de los términos asintóticos a Cλim a la suma mencionada anteriormente, y luego necesitamos estimar la suma.

La prueba de Flajolet y Sedgewick es quizás más simple, pero menos elemental. Su punto de partida es la función generadora racional de cn(L) , e implica la inducción sobre el número de magnitudes de polo (!). La idea básica es que todos los valores propios del módulo máximo son raíces de la unidad (si están normalizados por su módulo), debido a un teorema (moderadamente fácil) de Berstel. Al elegir un d apropiado dy mirar palabras de longitud dm+a , todos estos valores propios se vuelven reales. Considerando la expansión de la fracción parcial, obtenemos que si el valor propio del módulo máximo "sobrevive", entonces determina las asintóticas, que son de la forma Cnkλn. De lo contrario, encontramos una nueva función generadora racional que corresponde solo a palabras de esta longitud (usando un producto Hadamard), y repetimos el argumento. La cantidad mencionada sigue disminuyendo, y finalmente encontramos los asíntóticos deseados; podría tener que crecer en el proceso, para reflejar todo lo que sucede en los pasos inductivos.d

¿Existe una prueba simple y elemental para la propiedad asintótica de ?cn(L)

Yuval Filmus
fuente
¿A qué "propiedad asintótica" te refieres, la que está arriba?
Raphael
Exactamente esa propiedad.
Yuval Filmus
Para el caso reducible, ¿no hay límites combinatorios simples (tal vez obtenidos considerando subconjuntos de rutas y multisets de rutas)?
András Salamon
Hay límites fáciles, pero probablemente pierdas factores polinómicos allí. Hay una suma con muchos términos polinomiales, y podemos estimarla usando el término más grande. Sin embargo, esto no nos dará el asintótico correcto, ya que los otros términos decaen bastante rápido. Quizás sea posible una estimación con una integral, pero eso ya se está volviendo un poco complicado.
Yuval Filmus
1
en general, encontrar pruebas alternativas o más elementales de problemas puede ser muy difícil y es principalmente un ejercicio teórico ... ¿hay alguna otra motivación / bkg / aplicación? sugiero migrar a la teoría.
vzn

Respuestas:

3

El argumento que ha esbozado parece estar en línea con el tratamiento de Richard Stanley del Método de matriz de transferencia en combinatoria enumerativa, Volumen 1 (enlace: pp 573; impresión: pp 500).

Comienza con la función generadora y la desempaqueta considerando los dígrafos y los factores permitidos y prohibidos. Luego se resume en monoides gratuitos, donde usa una versión refinada de las sumas que usted dio para demostrar:

BABB(λ)=(IB(λ))1

Después de trabajar en algunas aplicaciones, también cierra la sección discutiendo los productos Hadamard en relación con los poliominoes convexos horizontalmente.

JSS
fuente
¿Puedes señalar un teorema en el texto de Stanley que proporcione estimaciones asintóticas?
Yuval Filmus
No puedo encontrar ninguna referencia inmediata y explícita en Stanley, pero Flajolet y Sedgewick reconocen su influencia en su tratamiento del método de la matriz de transferencia en la sección V.6. En particular, el Corolario V.1 subsume los Teoremas anteriores (V.7, V.8) que parecen seguir su línea de razonamiento. También parecen seguir el esquema de Stanley que comienza en la subsección V.5, donde la Propuesta V.6 corresponde al Teorema de Stanley 4.7.2 y Corolario 4.7.3
JSS
Lo que busco específicamente es el análisis asintótico. La fórmula exacta para el número de palabras de longitud dada, dada por el método de matriz de transferencia, es lo que doy por sentado.
Yuval Filmus