16

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 :).

Community
  • 1
R B
  • 9,448
  • 5
  • 34
  • 74
  • The word "acyclic" doesn't appear in the linked question. Who suggested that computing $|L(M)|$ is #P-hard for an acyclic NFA $M$? – Tyson Williams Aug 27 '14 at 21:31
  • @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". – R B Aug 27 '14 at 21:44
  • @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. – R B Aug 27 '14 at 21:46
  • I am fine with your use of "suggested", understand that it only makes sense to count something if it is finite, and agree that considering an acyclic state graph is easier. I just don't see how this questions was suggested from the linked question. – Tyson Williams Aug 29 '14 at 17:57
  • 2
    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). – Tsuyoshi Ito Aug 31 '14 at 12:47
  • 8
    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. – Tsuyoshi Ito Aug 31 '14 at 15:06

1 Answers1

11

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

ricardorr
  • 541
  • 5
  • 14