2025/06/30 by Meel, Kuldeep S., de Colnet, Alexis · 1 citation
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2506.23561
#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 O(n17m17ε-14log(δ-1)), where m is the number of states in the automaton, δ∈ (0,1] is the confidence parameter, and ε > 0 is the tolerance parameter (typically smaller than 1). The current best FPRAS achieved a significant improvement in the time complexity relative to the first FPRAS and obtained FPRAS with time complexity O((n10m2 + n6m3)ε-4log2(δ-1)). The complexity of the improved FPRAS is still too intimidating to attempt any practical implementation. In this paper, we pursue the quest for practical FPRAS for #NFA by presenting a new algorithm with a time complexity of O(n2m3log(nm)ε-2log(δ-1)). Observe that evaluating whether a word of length n is accepted by an NFA has a time complexity of O(nm2). Therefore, our proposed FPRAS achieves sub-quadratic complexity with respect to membership checks.