# IASCAR: Incremental Answer Set Counting by Anytime Refinement

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 95 references that are in the map.
- First posted on arXiv 13 Nov 2023.

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

- [The Model Counting Competition 2020](https://mlsanity.com/paper/2012.01323/) (2020)
- [Distribution-Aware Sampling and Weighted Model Counting for SAT](https://mlsanity.com/paper/1404.2984/) (2014)
- [Answer Set Solving with Bounded Treewidth Revisited](https://mlsanity.com/paper/1702.02890/) (2017)
- [Design and Results of the Second International Competition on Computational Models of Argumentation](https://mlsanity.com/paper/1909.00621/) (2019)
- [Rushing and Strolling among Answer Sets -- Navigation Made Easy](https://mlsanity.com/paper/2112.07596/) (2021)
- [Treewidth-aware Reductions of Normal ASP to SAT -- Is Normal ASP Harder than SAT after All?](https://mlsanity.com/paper/2210.03553/) (2022)
- [Exploiting Database Management Systems and Treewidth for Counting](https://mlsanity.com/paper/2001.04191/) (2020)
- [Benchmarking Crimes: An Emerging Threat in Systems Security](https://mlsanity.com/paper/1801.02381/) (2018)
- [Utilizing Treewidth for Quantitative Reasoning on Epistemic Logic Programs](https://mlsanity.com/paper/2108.03022/) (2021)
- [On Hashing-Based Approaches to Approximate DNF-Counting](https://mlsanity.com/paper/1710.05247/) (2017)
- [Towards Faster Reasoners By Using Transparent Huge Pages](https://mlsanity.com/paper/2004.14378/) (2020)

## Built on by (most cited first, 2 of 2)

- [Answer Set Counting and its Applications](https://mlsanity.com/paper/2502.09231/) (2025)
- [Counting Answer Sets of Disjunctive Answer Set Programs](https://mlsanity.com/paper/2507.11655/) (2025)

## Abstract (arXiv)

Answer set programming (ASP) is a popular declarative programming paradigm with various applications. Programs can easily have many answer sets that cannot be enumerated in practice, but counting still allows quantifying solution spaces. If one counts under assumptions on literals, one obtains a tool to comprehend parts of the solution space, so-called answer set navigation. However, navigating through parts of the solution space requires counting many times, which is expensive in theory. Knowledge compilation compiles instances into representations on which counting works in polynomial time. However, these techniques exist only for CNF formulas, and compiling ASP programs into CNF formulas can introduce an exponential overhead. This paper introduces a technique to iteratively count answer sets under assumptions on knowledge compilations of CNFs that encode supported models. Our anytime technique uses the inclusion-exclusion principle to improve bounds by over- and undercounting systematically. In a preliminary empirical analysis, we demonstrate promising results. After compiling the input (offline phase), our approach quickly (re)counts.