Alladi Ramakrishnan Hall

A faster FPRAS for \#NFA

Sourav Chakraborty

ISI Kolkata

Given a non-deterministic finite automaton (NFA) $A$ with $m$ states, and a natural number $n$ (presented in unary), the \#NFA problem asks to determine the size of the set of words of length $n$ accepted by $A$. While the corresponding decision problem of checking the emptiness of $A$ is solvable in polynomial time, the \#NFA problem is known to be \#P-hard. Recently, the long-standing open question --- whether there is an FPRAS (fully polynomial time randomized approximation scheme) for \#NFA --- was resolved by Arenas, Croquevielle, Jayaram, and Riveros in ACJR19. The authors demonstrated the existence of a fully polynomial randomized approximation scheme with a time complexity of $O(m^{17}n^{17}\frac{1}{\epsl^{14}})$, for a given tolerance parameter $ \epsl$.

Given the prohibitively high time complexity in terms of each of the input parameters, and considering the widespread application of approximate counting (and sampling) in various tasks in Computer Science, a natural question arises: is there a faster FPRAS for \#NFA that can pave the way for the practical implementation of approximate \#NFA tools? In this work, we answer this question in the positive.

This is based on a recent work that is accepted in PODS 2024.