Towards practical FPRAS for #NFA: Exploiting the Power of Dependence

Kuldeep S. Meel, Alexis de Colnet

#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 appr…