Leveraging tree automata approximation results for efficient sampling and counting...
summary
Claim: sharp TA admits an FPRAS and that polynomial-time approximation for counting and almost-uniform sampling on a widely used fragment—structured DNNF—follows by encoding assignments as labeled trees and building a tree automaton that enforces the structure mapping. Construction uses top-down/bottom-up tree automata states tied to DNNF AND-splits, parsimonious reduction from SDNNF to TA, and complexity links to SpanL/SpanP; result is theoretical and works, but practical performance remains unclear.
AI-written summary · about