IASCAR: Incremental Answer Set Counting by Anytime Refinement

Johannes Klaus FichteJohannes Klaus Fichte, Sarah Alice GagglSarah Alice Gaggl, Markus HecherMarkus Hecher, Dominik RusovacDominik Rusovac

ISBN: 978-3-031-15707-3
Download
DOI Link

Johannes Klaus Fichte, Sarah Alice Gaggl, Markus Hecher, Dominik Rusovac
IASCAR: Incremental Answer Set Counting by Anytime Refinement
In Georg Gottlob, Daniela Inclezan, Marco Maratea, eds., Proceedings of the 16th International Conference on Logic Programming and Non-monotonic Reasoning (LPNMR 2022), volume 13416 of Lecture Notes in Computer Science, 217-230, August 2022. Springer International Publishing

Details
Bibtex

KurzfassungAbstract
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.
Bemerkung: Note: Honorable mention
Projekt:Project: CPEC, NAVAS
Forschungsgruppe:Research Group: Logische Programmierung und Argumentation

@inproceedings{FGHR2022,
  author    = {Johannes Klaus Fichte and Sarah Alice Gaggl and Markus Hecher and
               Dominik Rusovac},
  title     = {IASCAR: Incremental Answer Set Counting by Anytime Refinement},
  editor    = {Georg Gottlob and Daniela Inclezan and Marco Maratea},
  booktitle = {Proceedings of the 16th International Conference on Logic
               Programming and Non-monotonic Reasoning (LPNMR 2022)},
  series    = {Lecture Notes in Computer Science},
  volume    = {13416},
  publisher = {Springer International Publishing},
  year      = {2022},
  month     = {August},
  pages     = {217-230},
  doi       = {https://doi.org/10.1007/978-3-031-15707-3_17}
}