27
$\begingroup$

For a regular language $L$, let $c_n(L)$ be the number of words in $L$ of length $n$. Using Jordan canonical form (applied to the unannotated transition matrix of some DFA for $L$), one can show that for large enough $n$, $$ c_n(L) = \sum_{i=1}^k P_i(n) \lambda_i^n, $$ where $P_i$ are complex polynomials and $\lambda_i$ are complex "eigenvalues". (For small $n$, we may have additional terms of the form $C_k[n=k]$, where $[n=k]$ is $1$ if $n=k$ and $0$ otherwise. These correspond to Jordan blocks of size at least $k+1$ with eigenvalue $0$.)

This representation seems to imply that if $L$ is infinite then asymptotically, $c_n(L) \sim C n^k \lambda^n$ for some $C,\lambda>0$. However, this is patently false: for the language $L$ over $\{0,1\}$ of all words of even length, $c_{2n}(L) = 2^{2n}$ but $c_{2n+1}(L) = 0$. This suggests that for some $d$ and for all $a \in \{0,\ldots,d-1\}$, either $c_{dm+a}(L) = 0$ for large enough $m$ or $c_{dm+a} \sim C_a (dm+a)^{k_a} \lambda_a^{dm+a}$. This is proved in Flajolet & Sedgewick (Theorem V.3), who attribute the proof to Berstel.

The proof provided by Flajolet and Sedgewick is somewhat technical; so technical, in fact, that they only sketch it. I attempted a more elementary proof using Perron-Frobenius theory. We can regard the transition graph of the DFA as a digraph. If the digraph is primitive then the result follows almost directly from the Perron-Frobenius theorem. If the digraph is irreducible but imprimitive with index $r$, then by considering the "$r$th power" of the DFA (each transition corresponds to $r$ symbols), we get the same result. The difficult case is when the digraph is reducible. We can reduce to the case of a path of strongly connected components, and then we get the result by estimating sums of the form $$ \sum_{m_1+\cdots+m_k=m} \prod_{i=1}^k \lambda_i^{m_i}. $$ (Each such sum corresponds to a particular way of accepting a word, going through the different components in a certain way.) This sum, in turn, can be estimated by pinpointing the largest term, which corresponds to $m_i \propto \log \lambda_i$. For every eigenvalue which is repeated $r$ times, we get an extra factor of $\Theta(m^{r-1})$.

The proof has its rough edges: in the reducible case, we need to pass from terms asymptotic to $C \lambda_i^m$ to the sum mentioned above, and then we need to estimate the sum.

The proof by Flajolet and Sedgewick is perhaps simpler, but less elementary. Its starting point is the rational generating function of $c_n(L)$, and it involves induction on the number of pole magnitudes (!). The basic idea is that all eigenvalues of maximal modulus are roots of unity (if normalized by their modulus), due to a (moderately easy) theorem of Berstel. Choosing an appropriate $d$ and looking at words of length $dm+a$, all these eigenvalues become real. Considering the partial fraction expansion, we get that if the eigenvalue of maximal modulus "survives", then it determines the asymptotics, which are of the form $Cn^k\lambda^n$. Otherwise, we find a new rational generating function which corresponds just to words of this length (using an Hadamard product), and repeat the argument. The aforementioned quantity keeps decreasing, and so eventually we find the desired asymptotics; $d$ might have to grow in the process, to reflect everything that happens in the inductive steps.

Is there a simple and elementary proof for the asymptotic property of $c_n(L)$?

$\endgroup$
  • $\begingroup$ Which "asymptotic property" are you referring to, the one right at the top? $\endgroup$ – Raphael Apr 16 '13 at 9:30
  • $\begingroup$ Exactly that property. $\endgroup$ – Yuval Filmus Apr 16 '13 at 17:19
  • $\begingroup$ For the reducible case, are there no simple combinatorial bounds (perhaps obtained by considering subsets of paths, and multisets of paths)? $\endgroup$ – András Salamon Apr 27 '13 at 17:27
  • $\begingroup$ There are easy bounds, but you probably lose polynomial factors there. There is a sum with polynomially many terms, and we can estimate it using the largest term. However, this isn't going to give us the correct asymptotic, since the other terms decay quite quickly. Perhaps an estimate with an integral is possible, but that is already getting a bit messy. $\endgroup$ – Yuval Filmus Apr 28 '13 at 4:47
  • 1
    $\begingroup$ generally, finding alternative or more elementary proofs of problems can be very hard and is mostly a theoretical exercise... is there any further motivation/bkg/application? suggest migrate to cstheory. $\endgroup$ – vzn Apr 30 '13 at 2:32
3
$\begingroup$

The argument you have sketched appears to be in line with Richard Stanley's treatment of the Transfer-Matrix Method in Enumerative Combinatorics, Volume 1 (link: pp 573; print: pp 500).

He starts with the generating function, and unpacks it by considering digraphs and permissible and prohibited factors. He then abstracts to free monoids, where he uses a refined version of the sums you gave to prove:

4.7.11 Proposition Let $B$ be a subset of $A^*$ that freely generates $B$. Then $B^*(\lambda)=(I-B(\lambda))^{-1}$

After working through some applications, he likewise closes the section by discussing Hadamard products in relation to horizontally-convex polyominoes.

$\endgroup$
  • $\begingroup$ Can you point at a theorem in Stanley's text giving asymptotic estimates? $\endgroup$ – Yuval Filmus Jun 13 '14 at 1:13
  • $\begingroup$ I can't find any immediate, explicit reference in Stanley, but Flajolet and Sedgewick do acknowledge his influence on their treatment of the transfer matrix method in section V.6. In particular, Corollary V.1 subsumes previous Theorems (V.7, V.8) which seem to follow your line of reasoning. They also appear to follow Stanley's outline starting in subsection V.5, where Proposition V.6 corresponds to Stanley's Theorem 4.7.2 and Corollary 4.7.3 $\endgroup$ – JSS Jun 13 '14 at 20:43
  • $\begingroup$ What I'm specifically looking for is asymptotic analysis. The exact formula for the number of words of given length, given by the transfer matrix method, is what I take for granted. $\endgroup$ – Yuval Filmus Jun 13 '14 at 23:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.