Counting Answer Sets via Dynamic Programming
While the solution counting problem for propositional satisfiability (#SAT) has received renewed attention in recent years, this research trend has not affected other AI solving paradigms like answer set programming (ASP). Although ASP solvers are designed to enumerate all solutions, and counting can therefore be easily done, the involved materialization of all solutions is a clear bottleneck for the counting problem of ASP (#ASP). In this paper we propose dynamic programming-based #ASP algorithms that exploit the structure of the underlying (ground) ASP program. Experimental results for a prototype implementation show promise when compared to existing solvers.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
IASCAR: Incremental Answer Set Counting by Anytime Refinement
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…
Solving Decision Theory Problems with Probabilistic Answer Set Programming
Solving a decision theory problem usually involves finding the actions, among a set of possible ones, which optimize the expected reward, possibly accounting for the uncertainty of the environment. In this paper, we intr…
Answer Set Solving with Bounded Treewidth Revisited
Parameterized algorithms are a way to solve hard problems more efficiently, given that a specific parameter of the input is small. In this paper, we apply this idea to the field of answer set programming (ASP). To this e…
Counting Answer Sets of Disjunctive Answer Set Programs
Answer Set Programming (ASP) provides a powerful declarative paradigm for knowledge representation and reasoning. Recently, counting answer sets has emerged as an important computational problem with applications in prob…
Exact ASP Counting with Compact Encodings
Answer Set Programming (ASP) has emerged as a promising paradigm in knowledge representation and automated reasoning owing to its ability to model hard combinatorial problems from diverse domains in a natural way. Buildi…