Before revision:  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.
After revision: 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 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.