POPL 2027
Sun 10 - Sat 16 January 2027 Mexico City, Mexico

Given a nondeterministic finite automaton $\mathcal{A}$ and a length $n$ in unary, the problem $#\mathsf{NFA}$ seeks to compute the number of words of length $n$ accepted by $\mathcal{A}$. A celebrated result of Arenas, Croquevielle, Jayaram, and Riveros established that $#\mathsf{NFA}$ admits a fully polynomial-time randomized approximation scheme (FPRAS), and subsequent work has brought the running time down to $O(n^2m^3\log(nm),\epsilon^{-2}\log(1/\delta))$ for an NFA with $m$ states. All of these algorithms, however, assume an explicitly represented alphabet, whereas automata arising from programs, strings, and structured data are naturally \emph{symbolic}: transitions carry predicates over a large concrete alphabet $\mathbb{D}$, guards may overlap, and a single word may be accepted through many runs.

In this work, we design the first FPRAS for counting the words of length $n$ accepted by a symbolic NFA. Our algorithm accesses the guards only through three elementary operations, namely membership tests, approximate counting, and almost-uniform sampling. Further, the algorithm does not construct \emph{minterms} or Boolean combinations of guards, and only poses these membership, approximate counting and almost-uniform sampling queries for the guards that actually appear on the transitions of the input automaton. Our FPRAS runs in time polynomial in the size of the symbolic automaton, $n$, $\epsilon^{-1}$, and $\log(1/\delta)$, with no dependence on $|\mathbb{D}|$ beyond the cost of the elementary operations.
With unit-cost oracle operations, the algorithm makes $O(n^2,|\Delta|\log(n|\Delta|),\epsilon^{-2}\log(1/\delta))$ counting and sampling queries for a symbolic NFA with transition set $\Delta$, and its running time, instantiated on an explicit alphabet of constant size, matches the best known bound for $#\mathsf{NFA}$.
To the best of our knowledge, this is the first approximate-counting result for automata modulo predicates. The analysis contends with two phenomena absent from the explicit-alphabet setting: sampled single-letter extensions, whose collisions we fold into an exact-equality martingale descent, and approximate oracles, whose drift we absorb into per-word weights and graded target intervals. Finally, we machine-check the probabilistic correctness argument in the Lean 4 proof assistant: under explicit structural and oracle hypotheses, the development derives the $(\epsilon,\delta)$ guarantee for a finite-coin realization of the core estimator, with no \texttt{sorry} or non-standard axioms.

Note to reviewers. The results in this paper have been mechanized in Lean. The (anonymized) proof files are attached as supplementary material. They are also available for review here: https://anonymous.4open.science/r/lean-symbolicnfa-0B49/