Pruning external minimality checking for answer set programs using semantic dependencies

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