• Classified by Research Topic • Sorted by Date • Classified by Publication Type •
#CFG and #DNNF admit FPRAS.
Kuldeep S. Meel, and Alexis de Colnet.
In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pp. 5978–6010, 2026.
We provide the first fully polynomial-time randomized approximation scheme for the following two counting problems: 1. Given a Context-Free Grammar G over alphabet Sigma , count the number of words of length exactly n generated by G 2. Given a circuit phi in Decomposable Negation Normal Form (DNNF) over the set of Boolean variables X , compute the number of assignments to X such that phi evaluates to 1. Finding polynomial time algorithms for the aforementioned problems has been a longstanding open problem. Prior work could either only obtain a quasi-polynomial runtime or a polynomial-time randomized approximation scheme for non-deterministic finite automata and non-deterministic tree automata.
@inproceedings{MdC26,
title={\#CFG and \#DNNF admit FPRAS},
author={Meel, Kuldeep S. and de Colnet, Alexis},
booktitle={
Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)
},
pages={5978--6010},
year={2026},
bib2html_rescat={Counting},
bib2html_pubtype={Refereed Conference},
bib2html_dl_pdf={https://doi.org/10.1137/1.9781611978971.213},
abstract={
We provide the first fully polynomial-time randomized approximation scheme
for the following two counting problems:
1.
Given a Context-Free Grammar G
over alphabet Sigma
, count the number of words of length exactly n
generated by G
2.
Given a circuit phi
in Decomposable Negation Normal Form (DNNF) over the set of Boolean
variables X
, compute the number of assignments to X
such that phi
evaluates to 1.
Finding polynomial time algorithms for the aforementioned problems has been
a longstanding open
problem. Prior work could either only obtain a quasi-polynomial runtime or a
polynomial-time
randomized approximation scheme for non-deterministic finite automata and
non-deterministic
tree automata.
},
}
Generated by bib2html.pl (written by Patrick Riley with layout from Sanjit A. Seshia ) on Tue Apr 28, 2026 01:27:21