IASCAR: Incremental Answer Set Counting by Anytime Refinement

Publikation: Beitrag in FachzeitschriftForschungsartikelBeigetragenBegutachtung

Beitragende

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.

Details

OriginalspracheEnglisch
Seiten (von - bis)505-532
Seitenumfang28
FachzeitschriftTheory and practice of logic programming : TPLP
Jahrgang24
Ausgabenummer3
Frühes Online-Datum21 Feb. 2024
PublikationsstatusVeröffentlicht - Mai 2024
Peer-Review-StatusJa

Externe IDs

Scopus 85185785212
ORCID /0000-0003-2425-6089/work/173986250

Schlagworte

Schlagwörter

  • ASP, answer set counting, knowledge compilation