Asymptotyka liczby słów w języku regularnym o zadanej długości

Dla języka regularnego , niech będzie liczbą słów w o długości . Stosując kanoniczną postać Jordana (zastosowaną do niezanotowanej macierzy przejścia dla niektórych DFA dla ), można wykazać, że dla wystarczająco dużych , gdzie wielomiany są złożone i $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$ są złożonymi „wartościami własnymi”. (Dla małych

możemy mieć dodatkowe warunki postaci

, gdzie

wynosi

jeśli

a w przeciwnym razie

Odpowiadają one blokom Jordana o wielkości co najmniej

z wartość własna

)

n

$n$

C_{k} [n = k]

$C_k[n=k]$

[n = k]

$[n=k]$

1

$1$

n = k

$n=k$

0

$0$

k + 1

$k+1$

0

$0$

Ta reprezentacja wydaje się sugerować, że jeśli jest nieskończony, to asymptotycznie, dla niektórych . Jest to jednak wyraźnie nieprawda: dla języka ponad wszystkich słów o parzystej długości ale $L$ $c_n(L) \sim C n^k \lambda^n$ $C,\lambda>0$ $L$ $\{0,1\}$ $c_{2n}(L) = 2^{2n}$ . Sugeruje to, że dla niektórych i dla wszystkich albo dla wystarczająco dużej lub . Jest to udowodnione wFlajolet i Sedgewick $c_{2n+1}(L) = 0$ $d$ $a \in \{0,\ldots,d-1\}$ $c_{dm+a}(L) = 0$ $m$ $c_{dm+a} \sim C_a (dm+a)^{k_a} \lambda_a^{dm+a}$ (Twierdzenie V.3), którzy przypisują dowód Berstelowi.

Dowody dostarczone przez Flajolet i Sedgewick są nieco techniczne; tak techniczne, że tylko szkicują. Próbowałem bardziej elementarnego dowodu, używając teorii Perrona-Frobeniusa. Możemy traktować wykres przejścia DFA jako wykres. Jeśli digraf jest prymitywny, wynik wynika prawie bezpośrednio z twierdzenia Perrona-Frobeniusa. Jeśli digraph jest nieredukowalne ale imprimitive z indeksu , a następnie rozważając „ th moc” DFA (każda odpowiada przejściu do symboli), możemy uzyskać ten sam rezultat. Trudny przypadek występuje wtedy, gdy wykrój można zredukować. Możemy zredukować do przypadku ścieżki silnie połączonych komponentów, a następnie uzyskujemy wynik, szacując sumy postaci $r$ $r$ $r$ (Każda taka suma odpowiada konkretnemu sposobowi akceptacji słowa, przechodząc przez różne składniki w określony sposób.) Z kolei sumę tę można oszacować, wskazując największy termin, który odpowiada. Za każdą wartość własną, która jest powtarzanarazy, otrzymujemy dodatkowy współczynnik.

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

$\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})$

$C \lambda_i^m$

$c_n(L)$ $d$ $dm+a$ $Cn^k\lambda^n$ $d$

$c_n(L)$

formal-languages reference-request regular-languages asymptotics combinatorics Yuval Filmus
źródło

Do której „właściwości asymptotycznej” masz na myśli, tę na samej górze?

Raphael

Dokładnie ta właściwość.

Yuval Filmus

Czy w przypadku przypadku redukowalnego nie ma prostych granic kombinatorycznych (być może uzyskanych przez rozważenie podzbiorów ścieżek i multiset ścieżek)?

András Salamon

Istnieją proste granice, ale prawdopodobnie tracisz tam czynniki wielomianowe. Jest suma z wielomianowo wieloma terminami i możemy ją oszacować za pomocą największego terminu. Nie da nam to jednak prawidłowej asymptotyki, ponieważ inne warunki rozkładają się dość szybko. Być może oszacowanie z całką jest możliwe, ale robi się już trochę nieporządne.

Yuval Filmus

ogólnie rzecz biorąc, znalezienie alternatywnych lub bardziej elementarnych dowodów problemów może być bardzo trudne i jest w większości ćwiczeniem teoretycznym ... czy jest jakaś dodatkowa motywacja / kg / aplikacja? sugeruj migrację do cstheory.

dniu

Naszkicowany przez ciebie argument wydaje się być zgodny z podejściem Richarda Stanleya do metody Transfer-Matrix w Enumerative Combinatorics, tom 1 (link: pp 573; print: pp 500).

Zaczyna od funkcji generowania i rozpakowuje ją, biorąc pod uwagę digrafy oraz czynniki dopuszczalne i zabronione. Następnie abstraktuje za darmo monoidy, w których używa wyrafinowanej wersji sum, które podałeś, aby udowodnić:

$B$ $A^*$ $B$ $B^*(\lambda)=(I-B(\lambda))^{-1}$

Po zapoznaniu się z niektórymi aplikacjami, on również zamyka sekcję, omawiając produkty Hadamard w odniesieniu do polomino-wypukłych poziomo.

JSS
źródło

Czy możesz wskazać twierdzenie w tekście Stanleya, dające asymptotyczne oszacowania?

Yuval Filmus,

Nie mogę znaleźć żadnego bezpośredniego, wyraźnego odniesienia w Stanley, ale Flajolet i Sedgewick potwierdzają jego wpływ na ich traktowanie metody macierzy transferowej w rozdziale V.6. W szczególności następstwo V.1 opiera się na poprzednich Twierdzeniach (V.7, V.8), które wydają się podążać za tobą. Wydają się również podążać za konspektem Stanleya, zaczynając od podrozdziału V.5, gdzie Twierdzenie V.6 odpowiada Twierdzeniu Stanleya 4.7.2 i następstwom 4.7.3

JSS

Szczególnie szukam analizy asymptotycznej. Dokładną formułę liczby słów o danej długości, podaną metodą macierzy transferowej, uważam za pewnik.

Yuval Filmus

Asymptotyka liczby słów w języku regularnym o zadanej długości

Odpowiedzi: