IASCAR: Incremental Answer Set Counting by Anytime Refinement
Open Access
- 21 February 2024
- journal article
- research article
- Published by Cambridge University Press (CUP) in Theory and Practice of Logic Programming
- Vol. 24 (3) , 505-532
Abstract
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 conjunctive normal form (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.Keywords
All Related Versions
This publication has 60 references indexed in Scilit:
- Clingraph: ASP-Based Visualization2022
- IASCAR: Incremental Answer Set Counting by Anytime Refinement2022
- A Practical Account into Counting Dung’s Extensions by Dynamic Programming2022
- Tunas - Fishing for Diverse Answer Sets: A Multi-shot Trade up Strategy2022
- Towards Faster Reasoners by Using Transparent Huge Pages2020
- Answer Set Solving with Bounded Treewidth Revisited2017
- The Design of the Seventh Answer Set Programming CompetitionLecture Notes in Computer Science, 2017
- An A-Prolog Decision Support System for the Space Shuttle2001
- Encoding planning problems in nonmonotonic logic programsLecture Notes in Computer Science, 1997
- Negation as Failure1978