Asymptotik der Anzahl der Wörter in einer regulären Sprache von gegebener Länge

Für eine reguläre Sprache sei die Anzahl der Wörter in der Länge . Verwendung Jordan kanonische Form (angewandt auf die unkommentierten bergangsmatrix einige DFA für ) kann man zeigen , dass für ausreichend großen , Dabei sind komplexe Polynome und komplexe "Eigenwerte". (Für kleine können wir zusätzliche Terme der Form haben , wobei ist , wenn , und $L$ $c_n(L)$ $L$ $n$ $L$ $n$

c_{n} (L) = \sum_{i = 1}^{k} P_{i} (n) λ_{i}^{n},

$c_n(L) = \sum_{i=1}^k P_i(n) \lambda_i^n,$

P_{i}

$P_i$

λ_{i}

$\lambda_i$

n

$n$

C_{k} [n = k]

$C_k[n=k]$

[n = k]

$[n=k]$

1

$1$

n = k

$n=k$

0

$0$ sonst. Dies entspricht Jordan-Blöcken mit einer Größe von mindestens mit dem Eigenwert )

k + 1

$k+1$

0

$0$

Diese Darstellung scheint zu implizieren, dass, wenn unendlich ist, für etwas asymptotisch ist . Dies ist jedoch offensichtlich falsch: Für die Sprache über aller Wörter mit gerader Länge gilt aber $L$ $c_n(L) \sim C n^k \lambda^n$ $C,\lambda>0$ $L$ $\{0,1\}$ $c_{2n}(L) = 2^{2n}$ . Dies legt nahe, dass für einige und für alle entweder $c_{2n+1}(L) = 0$ $d$ $a \in \{0,\ldots,d-1\}$ fürgroß genugoder . Dies wird inFlajolet & Sedgewick(Satz V.3)bewiesen, der den Beweis Berstel zuschreibt. $c_{dm+a}(L) = 0$ $m$ $c_{dm+a} \sim C_a (dm+a)^{k_a} \lambda_a^{dm+a}$

Der von Flajolet und Sedgewick vorgelegte Beweis ist etwas technisch; in der Tat so technisch, dass sie es nur skizzieren. Ich versuchte einen elementareren Beweis mit der Perron-Frobenius-Theorie. Wir können den Übergangsgraphen des DFA als einen Digraphen betrachten. Wenn der Digraph primitiv ist, folgt das Ergebnis fast direkt aus dem Perron-Frobenius-Theorem. Wenn der Digraph irreduzibel ist, aber nicht den Index , erhalten wir unter Berücksichtigung der " ten Potenz" des DFA (jeder Übergang entspricht Symbolen) dasselbe Ergebnis. Der schwierige Fall ist, wenn der Digraph reduzierbar ist. Wir können auf den Fall eines Pfades stark verbundener Komponenten reduzieren und erhalten dann das Ergebnis, indem wir Summen der Form schätzen $r$ $r$ $r$ (Jede solche Summe entspricht einer bestimmten Art und Weise, ein Wort zu akzeptieren, wobei die verschiedenen Komponenten auf eine bestimmte Art und Weise durchlaufen werden.) Diese Summe kann wiederum geschätzt werden, indem der größte Term bestimmt wird, der. Für jeden Eigenwert, dermalwiederholtwird, erhalten wir einen zusätzlichen Faktor von.

\sum_{m_{1} + \dots + m_{k} = m} \prod_{ich = 1}^{k} λ_{ich}^{m_{ich}} .

$\sum_{m_1+\cdots+m_k=m} \prod_{i=1}^k \lambda_i^{m_i}.$

m_{i} \propto \log λ_{i}

$m_i \propto \log \lambda_i$

r

$r$

Θ (m^{r - 1})

$\Theta(m^{r-1})$

Der Beweis hat seine Ecken und Kanten: in dem reduzierbaren Fall müssen wir von Begriffen asymptotischen passieren die Summe oben erwähnt, und dann müssen wir die Summe abzuschätzen. $C \lambda_i^m$

Der Beweis von Flajolet und Sedgewick ist vielleicht einfacher, aber weniger elementar. Ausgangspunkt ist die rationale Erzeugungsfunktion von , bei der die Anzahl der Polgrößen (!) Induziert wird. Die Grundidee ist, dass alle Eigenwerte des Maximalmoduls aufgrund eines (mäßig einfachen) Satzes von Berstel Wurzeln der Einheit sind (wenn durch ihren Modul normalisiert). Wenn Sie ein geeignetes auswählen und Wörter mit der Länge , werden alle diese Eigenwerte real. Unter Berücksichtigung der Teilbruchexpansion erhalten wir, dass, wenn der Eigenwert des Maximalmoduls "überlebt", er die Asymptoten bestimmt, die die Form $c_n(L)$ $d$ $dm+a$ . Andernfalls finden wir eine neue rationale Erzeugungsfunktion, die nur Wörtern dieser Länge entspricht (unter Verwendung eines Hadamard-Produkts), und wiederholen das Argument. Die vorgenannte Menge nimmt ständig ab, und so finden wir schließlich die gewünschten Asymptoten; dabei wachsen muss, um alles zu reflektieren, was in den induktiven Schritten passiert. $Cn^k\lambda^n$ $d$

Gibt es einen einfachen und elementaren Beweis für die asymptotische Eigenschaft von ? $c_n(L)$

formal-languages reference-request regular-languages asymptotics combinatorics Yuval Filmus
quelle

Auf welche "asymptotische Eigenschaft" beziehen Sie sich, die ganz oben?

Raphael

Genau diese Eigenschaft.

Yuval Filmus

Gibt es für den reduzierbaren Fall keine einfachen kombinatorischen Grenzen (möglicherweise erhalten durch Berücksichtigen von Teilmengen von Pfaden und von Mehrfachmengen von Pfaden)?

András Salamon

Es gibt einfache Grenzen, aber Sie verlieren dort wahrscheinlich Polynomfaktoren. Es gibt eine Summe mit polynomiell vielen Begriffen, und wir können sie unter Verwendung des größten Begriffs schätzen. Dies gibt uns jedoch nicht die richtige Asymptotik, da die anderen Ausdrücke ziemlich schnell verfallen. Vielleicht ist eine Schätzung mit einem Integral möglich, aber das wird schon ein bisschen chaotisch.

Yuval Filmus

Im Allgemeinen kann es sehr schwierig sein, alternative oder elementarere Beweise für Probleme zu finden. Dies ist meist eine theoretische Übung. Gibt es weitere Motivation / bkg / Anwendung? Schlagen Sie vor, nach cstheory zu migrieren.

vzn

Das von Ihnen skizzierte Argument scheint im Einklang mit Richard Stanleys Behandlung der Transfer-Matrix-Methode in Enumerative Combinatorics, Band 1 (Link: S. 573; Druck: S. 500) zu stehen.

Er beginnt mit der Erzeugungsfunktion und packt sie unter Berücksichtigung von Digraphen und zulässigen und verbotenen Faktoren aus. Anschließend abstrahiert er zu freien Monoiden, wobei er eine verfeinerte Version der von Ihnen angegebenen Beträge verwendet, um Folgendes zu beweisen:

4.7.11 Satz Sei eine Teilmenge von , die frei erzeugt . Dann ist $B$ $A^*$ $B$ $B^*(\lambda)=(I-B(\lambda))^{-1}$

Nachdem er einige Anwendungen durchgearbeitet hat, schließt er den Abschnitt ebenfalls mit der Diskussion von Hadamard-Produkten in Bezug auf horizontal konvexe Polyominoe.

JSS
quelle

Können Sie auf einen Satz in Stanleys Text verweisen, der asymptotische Schätzungen enthält?

Yuval Filmus

Ich kann in Stanley keine unmittelbare, explizite Referenz finden, aber Flajolet und Sedgewick erkennen seinen Einfluss auf ihre Behandlung der Übertragungsmatrixmethode in Abschnitt V.6 an. Insbesondere werden in Korollar V.1 frühere Theoreme (V.7, V.8) zusammengefasst, die Ihrer Argumentation zu folgen scheinen. Sie scheinen auch Stanleys Umriss zu folgen, der in Unterabschnitt V.5 beginnt, wo Satz V.6 Stanleys Satz 4.7.2 und Folgerung 4.7.3

JSS

Was ich speziell suche, ist asymptotische Analyse. Die genaue Formel für die Anzahl der Wörter mit der angegebenen Länge nach der Übertragungsmatrixmethode ist für mich selbstverständlich.

Yuval Filmus

Asymptotik der Anzahl der Wörter in einer regulären Sprache von gegebener Länge

Antworten: