Counting Answer Sets of Disjunctive Answer Set Programs
This addresses a computational bottleneck in probabilistic reasoning and network reliability analysis for researchers and practitioners in knowledge representation and reasoning, representing an incremental advance in ASP counting methods.
The paper tackled the problem of counting answer sets for disjunctive logic programs, which is challenging compared to normal programs, and introduced SharpASP-SR, a framework based on subtractive reduction to projected model counting, demonstrating significant performance improvements over existing counters, especially on instances with large answer set counts, and achieving state-of-the-art results with a hybrid approach.
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 probabilistic reasoning, network reliability analysis, and other domains. This has motivated significant research into designing efficient ASP counters. While substantial progress has been made for normal logic programs, the development of practical counters for disjunctive logic programs remains challenging. We present SharpASP-SR, a novel framework for counting answer sets of disjunctive logic programs based on subtractive reduction to projected propositional model counting. Our approach introduces an alternative characterization of answer sets that enables efficient reduction while ensuring that intermediate representations remain of polynomial size. This allows SharpASP-SR to leverage recent advances in projected model counting technology. Through extensive experimental evaluation on diverse benchmarks, we demonstrate that SharpASP-SR significantly outperforms existing counters on instances with large answer set counts. Building on these results, we develop a hybrid counting approach that combines enumeration techniques with SharpASP-SR to achieve state-of-the-art performance across the full spectrum of disjunctive programs.