Before revision:  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.
After revision:  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 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 in the fields of constraint satisfaction problems ( CSPs) , database systems, software verification, and knowledge compilation.