@COMMENT This file was generated by bib2html.pl <https://sourceforge.net/projects/bib2html/> version 0.94
@COMMENT written by Patrick Riley <http://sourceforge.net/users/patstg/>
@COMMENT This file came from Kuldeep S. Meel's publication pages at
@COMMENT http://www.comp.nus.edu.sg/~meel/publications/
@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.
  },
}