#CFG and #DNNF admit FPRAS
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 \(\varphi\) in Decomposable Negation Normal Form (DNNF) over the set of Boolean variables \(X\), compute the number of assignments to \(X\) such that \(\varphi\) evaluates to 1.
Fields of Study & Subjects
Complexity and Algorithms in Graphs
semigroups and automata theory
Machine Learning and Algorithms
Publication details
- Journal / source
- Society for Industrial and Applied Mathematics eBooks
- Publisher
- Society for Industrial and Applied Mathematics
- Pages
- 5978–6010
- Publication date
- 1 January 2026
- Language
- EN