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 …
In this work, we study the fundamental problems of counting and sampling traces that a regular language touches. Formally, one fixes the alphabet Sigma and an independence relation I subseteq Sigma x Sigma. The computational problems we address take …
Non-deterministic read-once branching programs, also known as non-deterministic free binary decision diagrams (nFBDD), are a fundamental data structure in computer science for representing Boolean functions. In this paper, we focus on #nFBDD, the …
Satisfiability Modulo Theory (SMT) solvers have advanced automated reasoning, solving complex formulas across discrete and continuous domains. Recent progress in propositional model counting motivates extending SMT capabilities toward model counting, …
Query evaluation over probabilistic databases is notoriously intractable – not only in combined complexity, but often in data complexity as well. This motivates the study of approximation algorithms, and particularly of combined FPRASes, with runtime …
Model counting is a fundamental problem that consists of determining the number of satisfying assignments for a given Boolean formula. The weighted variant, which computes the weighted sum of satisfying assignments, has extensive applications in …