 In this work, we  introduce the first fully polynomial time randomized approximation scheme (FPRAS) for counting the number of trees of size n accepted by a tree automaton, where n is given in unary , and the first polynomial time algorithm for sampling uniformly from this set of trees. Our results improve over the prior quasi-polynomial time randomized approximation scheme (QPRAS)and sampling algorithm of Gore, Jerrum, Kannan, Sweedyk, and Mahaney 97'. At the heart of our algorithm is a reduction to the problem of estimating the number of strings of length\neqP n accepted by a succinct non-deterministic finite automaton(NFA), which is an NFA where the transitions are labeled by succinctly encoded sets of symbols, whose sizes can be exponential in the encoding length. Assuming these sets of symbols can be efficiently sampled from, and their sizes approximated, we show that there is an FPRAS and polynomial time almost uniform sampler for succinct NFAs, which may be of independent interest. We demonstrate that, by applying our FPRAS for tree automata, we can obtain an FPRAS for many hitherto open problems in the fields of constraint satisfaction problems ( CSPs) , database systems, software verification, and knowledge compilation. Specifically, we obtain an FPRAS for counting solutions for CSPs that are acyclic or, more generally, that have bounded hypertree-width, which results in an FPRAS for counting the number of answers to conjunctive queries that are acyclic or which have bounded hypertree-width. Moreover, these results can be extended to unions of acyclic conjunctive queries, and to the more general class of unions of conjunctive queries with bounded hypertree-width . Finally, we also obtain FPRAS for the problems of counting the number of error threads in programs with nested call subroutines, and counting valid assignments to structured DNNF circuits.
Conjunctive queries are one of the most common classes of queries used in database systems, and the best studied in the literature. A seminal result of Grohe, Schwentick, and Segoufin (STOC 2004) demonstrates that when restricted to graphs, a class of conjunctive queries can be evaluated in polynomial time if and only if it has bounded treewidth. In this work, we extend this characterization to the counting problem for conjunctive queries. Specifically, for every class C of conjunctive queries with bounded treewidth, we introduce the first fully polynomial-time randomized approximation scheme (FPRAS) for counting answers to a query in C , and the first polynomial-time algorithm for sampling answers uniformly from a query in C. As a corollary, it follows that a class of conjunctive queries over graphs admits an FPRAS if and only if it has bounded treewidth (unless BPP\neqP). In fact, our FPRAS is more general, and also applies to conjunctive queries with bounded hypertree width, as well as unions of such queries. The key ingredient in our proof is the resolution of a fundamental counting problem from automata theory. Specifically, we demonstrate the first FPRAS and polynomial time sampler for the set of trees of size n accepted by a tree automaton, which improves the prior quasi-polynomial time randomized approximation scheme (QPRAS) and sampling algorithm of Gore, Jerrum, Kannan, Sweedyk, and Mahaney '97. We demonstrate how this algorithm can be used to obtain an FPRAS for many hitherto open problems , such as counting solutions to constraint satisfaction problems ( CSP) with bounded hypertree-width , counting the number of error threads in programs with nested call subroutines, and counting valid assignments to structured DNNF circuits.
A
Conjunctive queries are one of the most common classes of queries used in database systems, and the best studied in the literature. A seminal result of Grohe, Schwentick, and Segoufin (STOC 2004) demonstrates that when restricted to graphs, a class of conjunctive queries can be evaluated in polynomial time if and only if it has bounded treewidth.
A
extend this characterization to the counting problem for conjunctive queries. Specifically, for every class C of conjunctive queries with bounded treewidth, we
R
polynomial time
polynomial-time
R
the number of trees of size n accepted by a tree automaton, where n is given in unary
answers to a query in C
R
polynomial time
polynomial-time
R
uniformly from this set of trees. Our results improve over the prior quasi-polynomial time randomized approximation scheme (QPRAS)and sampling algorithm of Gore, Jerrum, Kannan, Sweedyk, and Mahaney 97'. At the heart of our algorithm is a reduction to the problem of estimating the number of strings of length
answers uniformly from a query in C. As a corollary, it follows that a class of conjunctive queries over graphs admits an FPRAS if and only if it has bounded treewidth (unless BPP
A
). In fact, our FPRAS is more general, and also applies to conjunctive queries with bounded hypertree width, as well as unions of such queries. The key ingredient in our proof is the resolution of a fundamental counting problem from automata theory. Specifically, we demonstrate the first FPRAS and polynomial time sampler for the set of trees of size
R
succinct non-deterministic finite automaton(NFA), which is an NFA where the transitions are labeled by succinctly encoded sets of symbols, whose sizes can be exponential in the encoding length. Assuming these sets of symbols can be efficiently sampled from, and their sizes approximated, we show that there is an FPRAS and polynomial time almost uniform sampler for succinct NFAs, which may be of independent interest. We demonstrate that, by applying our FPRAS for tree automata, we can
tree automaton, which improves the prior quasi-polynomial time randomized approximation scheme (QPRAS) and sampling algorithm of Gore, Jerrum, Kannan, Sweedyk, and Mahaney '97. We demonstrate how this algorithm can be used to
R
in the fields of
, such as counting solutions to
R
CSPs) , database systems, software verification, and knowledge compilation. Specifically, we obtain an FPRAS for counting solutions for CSPs that are acyclic or, more generally, that have bounded hypertree-width, which results in an FPRAS for counting the number of answers to conjunctive queries that are acyclic or which have bounded hypertree-width. Moreover, these results can be extended to unions of acyclic conjunctive queries, and to the more general class of unions of conjunctive queries
CSP)
R
. Finally, we also obtain FPRAS for the problems of
,