Tootfinder

Towards practical FPRAS for #NFA: Exploiting the Power of Dependence
Kuldeep S. Meel, Alexis de Colnet
https://arxiv.org/abs/2506.23561

Towards practical FPRAS for #NFA: Exploiting the Power of Dependence
#NFA refers to the problem of counting the words of length $n$ accepted by a non-deterministic finite automaton. #NFA is #P-hard, and although fully-polynomial-time randomized approximation schemes (FPRAS) exist, they are all impractical. The first FPRAS for #NFA had a running time of $\tilde{O}(n^{17}m^{17}\varepsilon^{-14}\log(δ^{-1}))$, where $m$ is the number of states in the automaton, $δ\in (0,1]$ is the confidence parameter, and $\varepsilon > 0$ is the tolerance parameter (typically s…