17
$\begingroup$

Let $M$ be an acyclic NFA.

Since $M$ is acyclic, $L(M)$ is finite.

In a related question, it was suggested that exact counting of the number of words accepted by $M$ is $\#P$-Complete.

The second answer for that question provides a counting algorithm, but only works for unambiguous NFAs (where every word is accepted by at most a single path).

Given an NFA $M$, can we approximate $|L(M)|$ in polynomial time?

As automata is a highly studied subject, I was surprised that I couldn't find anything about this, so if someone knows of a reference it'll be great :).

Improve this question
$\endgroup$
6
  • $\begingroup$ The word "acyclic" doesn't appear in the linked question. Who suggested that computing $|L(M)|$ is #P-hard for an acyclic NFA $M$? $\endgroup$
    – Tyson Williams
    Commented Aug 27, 2014 at 21:31
  • $\begingroup$ @TysonWilliams - it came up in the comment of the second answer. I'm not sure this is based on anything and this is why I used the word "suggested". $\endgroup$
    – R B
    Commented Aug 27, 2014 at 21:44
  • $\begingroup$ @TysonWilliams - In order for the question to make sense you either deal with acyclic automatons or count the words up to a given length. Dealing with acyclic automatons is easier, as you can find the limit on the word length and use the other algorithm. $\endgroup$
    – R B
    Commented Aug 27, 2014 at 21:46
  • 2
    $\begingroup$ As for the “suggested” part, the exact counting is indeed #P-complete. Membership to #P is clear, and #P-hardness can be shown by a simple reduction from the DNF counting problem (i.e., the problem of counting the number of satisfying assignments for a given DNF formula). $\endgroup$
    – Tsuyoshi Ito
    Commented Aug 31, 2014 at 12:47
  • 8
    $\begingroup$ Now I noticed that you had already posted the same question on cs.stackexchange.com and had already received an answer before posting the question here. I have to wonder why you posted this question here without revealing these facts. $\endgroup$
    – Tsuyoshi Ito
    Commented Aug 31, 2014 at 15:06

2 Answers 2

Reset to default
13
$\begingroup$

There exists a FPRAS (Fully Polynomial Randomized Approximation Scheme) for the problem of counting the words of length $n$ accepted by a NFA in the general case (without restricting to the acyclic NFA case).

The result was published this year on STOC, by Arenas, Croquevielle, Jayaram and Riveros.

Here is the talk https://youtu.be/tyK-uujHMLU and the paper https://arxiv.org/abs/1906.09226

Improve this answer
$\endgroup$
5
$\begingroup$

And now there is a faster FPRAS: https://arxiv.org/abs/2312.13320

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.