Asymptotique du nombre de mots dans une langue régulière de longueur donnée

28

Pour un langage régulier , soit le nombre de mots dans de longueur . En utilisant la forme canonique de Jordan (appliquée à la matrice de transition non annotée de certains DFA pour ), on peut montrer que pour un assez grand , où sont des polynômes complexes et sont des "valeurs propres" complexes. (Pour les petits , nous pouvons avoir des termes supplémentaires de la forme , où vaut si etc 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

cn(L)=je=1kPje(n)λjen,
PjeλjenCk[n=k][n=k]1n=k0autrement. Ceux-ci correspondent à des blocs de Jordan de taille au moins avec une valeur propre )0k+10

Cette représentation semble impliquer que si est infini, alors asymptotiquement, pour certains . Cependant, ceci est manifestement faux: pour le langage sur de tous les mots de longueur paire, mais . Cela suggère que pour certains et pour tous les , soit pour un assez grand ou c_ {dm + a} \ sim C_a (dm + a) ^ {k_a} \ lambda_a ^ {dm + a} . Cela est prouvé à Flajolet & Sedgewickc n ( L ) C n k λ n C , λ > 0 L { 0 , 1 } c 2 n ( L ) = 2 2 n c 2 n + 1 ( L ) = 0 d a { 0 , , d - 1 } c d m + a (Lcn(L)CnkλnC,λ>0L{0,1}c2n(L)=22nc2n+1(L)=0une{0,,-1}m c d m + aC a ( d m + a ) k a λ d m + a acm+une(L)=0mcm+uneCune(m+une)kuneλunem+une (Théorème V.3), qui attribue la preuve à Berstel.

La preuve fournie par Flajolet et Sedgewick est quelque peu technique; tellement technique, en fait, qu'ils ne font que le dessiner. J'ai tenté une preuve plus élémentaire en utilisant la théorie de Perron-Frobenius. Nous pouvons considérer le graphe de transition du DFA comme un digraphe. Si le digraphe est primitif, le résultat découle presque directement du théorème de Perron-Frobenius. Si le digraphe est irréductible mais imprimitif d'indice , alors en considérant la " ème puissance" du DFA (chaque transition correspond à r symboles), on obtient le même résultat. Le cas difficile est celui où le digraphe est réductible. On peut réduire au cas d'un chemin de composants fortement connectés, puis on obtient le résultat en estimant les sommes de la forme r r m 1 + + m k = m k i = 1 λ m i i .rrr

m1++mk=mje=1kλjemje.
(Chacune de ces sommes correspond à une façon particulière d'accepter un mot, en passant par les différents composants d'une certaine manière.) Cette somme, à son tour, peut être estimée en localisant le plus grand terme, qui correspond à mjebûcheλje . Pour chaque valeur propre qui est répétée r fois, nous obtenons un facteur supplémentaire de Θ(mr-1) .

La preuve a ses bords rugueux: dans le cas réductible, nous devons passer de termes asymptotiques à Cλjem à la somme mentionnée ci-dessus, puis nous devons estimer la somme.

La preuve de Flajolet et Sedgewick est peut-être plus simple, mais moins élémentaire. Son point de départ est la fonction génératrice rationnelle de , et elle implique une induction sur le nombre de magnitudes polaires (!). L'idée de base est que toutes les valeurs propres du module maximal sont des racines d'unité (si elles sont normalisées par leur module), en raison d'un théorème (modérément facile) de Berstel. En choisissant un approprié et en regardant des mots de longueur , toutes ces valeurs propres deviennent réelles. En considérant l'expansion de la fraction partielle, nous obtenons que si la valeur propre du module maximal "survit", alors elle détermine les asymptotiques, qui sont de la formecn(L)m+uneCnkλn. Sinon, nous trouvons une nouvelle fonction de génération rationnelle qui correspond uniquement aux mots de cette longueur (en utilisant un produit Hadamard), et répétons l'argument. La quantité susmentionnée continue de diminuer, et donc finalement nous trouvons les asymptotiques souhaitées; faudra peut-être grandir dans le processus pour refléter tout ce qui se passe dans les étapes inductives.

Existe-t-il une preuve simple et élémentaire de la propriété asymptotique de ?cn(L)

Yuval Filmus
la source
De quelle «propriété asymptotique» parlez-vous, celle qui se trouve tout en haut?
Raphael
Exactement cette propriété.
Yuval Filmus
Dans le cas réductible, n'y a-t-il pas de bornes combinatoires simples (peut-être obtenues en considérant des sous-ensembles de chemins et des ensembles multiples de chemins)?
András Salamon
Il y a des limites faciles, mais vous y perdez probablement des facteurs polynomiaux. Il existe une somme avec plusieurs termes polynomiaux, et nous pouvons l'estimer en utilisant le plus grand terme. Cependant, cela ne nous donnera pas la bonne asymptotique, car les autres termes se désintègrent assez rapidement. Peut-être qu'une estimation avec une intégrale est possible, mais cela devient déjà un peu compliqué.
Yuval Filmus
1
en général, trouver des preuves alternatives ou plus élémentaires des problèmes peut être très difficile et est surtout un exercice théorique ... y a-t-il une motivation / bkg / application supplémentaire? suggèrent de migrer vers la théorie.
vzn

Réponses:

3

L'argument que vous avez esquissé semble être conforme au traitement de Richard Stanley de la méthode de la matrice de transfert en combinatoire énumérative, volume 1 (lien: pp 573; impression: pp 500).

Il commence par la fonction de génération et la déballe en considérant les digraphes et les facteurs autorisés et interdits. Il résume ensuite les monoïdes libres, où il utilise une version raffinée des sommes que vous avez données pour prouver:

BUNEBB(λ)=(je-B(λ))-1

Après avoir travaillé sur certaines applications, il clôt également la section en discutant des produits Hadamard en relation avec les polyominos à convexe horizontale.

JSS
la source
Pouvez-vous indiquer un théorème dans le texte de Stanley donnant des estimations asymptotiques?
Yuval Filmus
Je ne trouve aucune référence immédiate et explicite dans Stanley, mais Flajolet et Sedgewick reconnaissent son influence sur leur traitement de la méthode de la matrice de transfert dans la section V.6. En particulier, Corollary V.1 résume les théorèmes précédents (V.7, V.8) qui semblent suivre votre raisonnement. Ils semblent également suivre le plan de Stanley à partir de la sous-section V.5, où la proposition V.6 correspond au théorème de Stanley 4.7.2 et au corollaire 4.7.3
JSS
Ce que je recherche spécifiquement, c'est une analyse asymptotique. La formule exacte du nombre de mots de longueur donnée, donnée par la méthode de la matrice de transfert, est ce que je tiens pour acquis.
Yuval Filmus