Answer Set Counting and its Applications
This work addresses efficiency bottlenecks in answer set counting for applications like network reliability, though it is incremental in improving existing methodologies.
The researchers tackled the problem of counting answer sets in Answer Set Programming by developing both exact (sharpASP) and approximate (ApproxASP) counters, with sharpASP outperforming existing methods on benchmarks and ApproxASP showing superior performance for network reliability estimation compared to traditional estimators and #SAT-based methods.
We have focused on Answer Set Programming (ASP), more specifically, answer set counting, exploring both exact and approximate methodologies. We developed an exact ASP counter, sharpASP, which utilizes a compact encoding for propositional formulas, significantly enhancing efficiency compared to existing methods that often struggle with inefficient encodings. Our evaluations indicate that sharpASP outperforms current ASP counters on several benchmarks. In addition, we proposed an approximate ASP counter, named ApproxASP, a hashing-based counter integrating Gauss-Jordan elimination within the ASP solver, clingo. As a practical application, we employed ApproxASP for network reliability estimation, demonstrating superior performance over both traditional reliability estimators and #SAT-based methods.