Given a nondeterministic finite automaton $\mathcal{A}$ (or a regular expression, or a regular grammar), can we efficiently compute the number $|L_k(\mathcal{A})|$ of accepted words of length $k$?

No, because in particular determining whether $\mathcal{A}$ accepts all words of length $k$ is PSPACE-complete ([1], Cor 4.16). But can we get any estimates on the growth rate of $|L_k(\mathcal{A})|$?

For instance, in the typical case where $\mathcal{A}$ has exponential growth (which is easy to detect; see [2]), we have that $|L_k(\mathcal{A})|=O(p(k)\lambda^k)$, for some polynomial $p$ and $\lambda$ the top eigenvalue of the transition matrix of the DFA corresponding to $\mathcal{A}$. Can we efficiently compute or approximate $\lambda$?

[1] http://ecommons.cornell.edu/bitstream/1813/6007/1/73-156.pdf

[2] http://arxiv.org/pdf/0711.4990.pdf


Your Answer

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

Browse other questions tagged or ask your own question.