16
$\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 :).

$\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$ Aug 27 '14 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
    Aug 27 '14 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
    Aug 27 '14 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$ Aug 31 '14 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$ Aug 31 '14 at 15:06
11
$\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

$\endgroup$

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.