Pruning external minimality checking for answer set programs using semantic dependencies

摘要

Answer set programming (ASP) has become an increasingly popular approach for declarative problem solving. In order to address the needs of applications, ASP has been extended in different approaches with means for interfacing the outside world, of which hex programs are one of the most powerful such extension that provides API-style interfaces to access arbitrary external sources of information and computation, respectively. Adhering to the principle of founded derivation, computing answer sets of hex programs requires an external (e-) minimality check for answer set candidates in order to prevent cyclic justifications via external sources. Due to the generic nature of external sources, the check can be a bottleneck in practice. To mitigate this, various optimizations have been developed previously, including the use of syntactic information about atom dependencies in order to detect cases when an e-minimality check can be avoided. However, the approach largely over-approximates the real dependencies due to the black-box nature of external sources. We thus consider in this work the use of semantic information for achieving better approximations. To this end, we introduce input-output (io-) dependencies for external sources, which intuitively link the occurrence of values in the result of a call to an external source to the occurrence of values in the input provided to this call. It appears that disposing of information about io-dependencies significantly increases the potential for pruning e-minimality checks, and an empirical evaluation exhibits a clear benefit of this approach. Moreover, we study semantic and computational properties of io-dependencies and provide algorithms for constructing and optimizing sets of io-dependencies. Our work aims at laying some foundations for the use of semantic dependency information in external source access from ASP. The results are not limited to hex programs, but may analogously be deployed to other approaches that integrate external sources into ASP, such as CLINGO or WASP with external propagators. Furthermore, the results may be applied in other parts of the hex program evaluation pipeline as well.