Fichte, J. K., Gaggl, S. A., Hecher, M., & Rusovac, D. (2022). IASCAR: Incremental Answer Set Counting by Anytime Refinement. In Logic Programming and Nonmonotonic Reasoning (pp. 217–230). Springer. http://hdl.handle.net/20.500.12708/142530
LPNMR 2022: 16th International Conference on Logic Programming and Non-monotonic Reasoning
en
Event date:
5-Sep-2022 - 9-Sep-2022
-
Event place:
Genua, Italy
-
Number of Pages:
14
-
Publisher:
Springer, Cham, Switzerland
-
Peer reviewed:
Yes
-
Keywords:
ASP; Answer set counting; Knowledge compilation
en
Abstract:
Answer set programming (ASP) is a popular declarative programming paradigm with various applications. Programs can easily have so many answer sets that they cannot be enumerated in practice, but counting still allows to quantify 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. But navigating through parts of the solution space requires counting many times, which is expensive in theory. There, 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. In this paper, we introduce a technique to iteratively count answer sets under assumptions on knowledge compilations of CNFs that encode supported models. Our anytime technique uses the principle of inclusion-exclusion to systematically improve bounds by over- and undercounting. In a preliminary empirical analysis we demonstrate promising results. After compiling the input (offline phase) our approach quickly (re)counts.
en
Project title:
Hybrid Parameterized Problem Solving in Practice: P32830-N (Fonds zur Förderung der wissenschaftlichen Forschung (FWF)) Revealing and Utilizing the Hidden Structure for Solving Hard Problems in AI: ICT19-065 (WWTF Wiener Wissenschafts-, Forschu und Technologiefonds)
-
Project (external):
DFG BMBF FWF
-
Project ID:
Grant TRR 248 project ID 389792660 Grant 01IS20056_NAVAS Y698