# Counting Answer Sets of Disjunctive Answer Set Programs

arXiv: https://arxiv.org/abs/2507.11655 · HTML: https://mlsanity.com/paper/2507.11655/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 15 of its 64 references that are in the map.
- First posted on arXiv 15 Jul 2025.

## Builds on (most cited first, 15 of 15)

- [Answering the "why" in Answer Set Programming - A Survey of Explanation Approaches](https://mlsanity.com/paper/1809.08034/) (2018)
- [The Seventh Answer Set Programming Competition: Design and Results](https://mlsanity.com/paper/1904.09134/) (2019)
- [Answer Set Solving with Bounded Treewidth Revisited](https://mlsanity.com/paper/1702.02890/) (2017)
- [Rushing and Strolling among Answer Sets -- Navigation Made Easy](https://mlsanity.com/paper/2112.07596/) (2021)
- [Stable Model Counting and Its Application in Probabilistic Logic Programming](https://mlsanity.com/paper/1411.5410/) (2014)
- [Computing LPMLN Using ASP and MLN Solvers](https://mlsanity.com/paper/1707.06325/) (2017)
- [Treewidth-aware Reductions of Normal ASP to SAT -- Is Normal ASP Harder than SAT after All?](https://mlsanity.com/paper/2210.03553/) (2022)
- [Projected Model Counting](https://mlsanity.com/paper/1507.07648/) (2015)
- [Exact ASP Counting with Compact Encodings](https://mlsanity.com/paper/2312.11936/) (2023)
- [On Lower Bounding Minimal Model Count](https://mlsanity.com/paper/2407.09744/) (2024)
- [Backdoors to Normality for Disjunctive Logic Programs](https://mlsanity.com/paper/1301.1391/) (2013)
- [IASCAR: Incremental Answer Set Counting by Anytime Refinement](https://mlsanity.com/paper/2311.07233/) (2023)
- [Minimal Model Counting via Knowledge Compilation](https://mlsanity.com/paper/2409.10170/) (2024)
- [Scalable Counting of Minimal Trap Spaces and Fixed Points in Boolean Networks](https://mlsanity.com/paper/2506.06013/) (2025)
- [An ASP-Based Framework for MUSes](https://mlsanity.com/paper/2507.03929/) (2025)

## Abstract (arXiv)

Answer Set Programming (ASP) provides a powerful declarative paradigm for knowledge representation and reasoning. Recently, counting answer sets has emerged as an important computational problem with applications in probabilistic reasoning, network reliability analysis, and other domains. This has motivated significant research into designing efficient ASP counters. While substantial progress has been made for normal logic programs, the development of practical counters for disjunctive logic programs remains challenging. We present SharpASP-SR, a novel framework for counting answer sets of disjunctive logic programs based on subtractive reduction to projected propositional model counting. Our approach introduces an alternative characterization of answer sets that enables efficient reduction while ensuring that intermediate representations remain of polynomial size. This allows SharpASP-SR to leverage recent advances in projected model counting technology. Through extensive experimental evaluation on diverse benchmarks, we demonstrate that SharpASP-SR significantly outperforms existing counters on instances with large answer set counts. Building on these results, we develop a hybrid counting approach that combines enumeration techniques with SharpASP-SR to achieve state-of-the-art performance across the full spectrum of disjunctive programs.