Dynamic Consistency Checking in Goal-Directed Answer Set Programming

ABSTRACT. One obstacle to goal-directed execution of answer set programs is that a valid answer set must satisfy the constraints imposed by every rule containing an odd loop over negation, even when those rules have no relation to a particular query. In this paper, we introduce a technique for dynamic consistency checking, under which only those constraints which are relevant to the partial answer set are tested. However, the algorithm guarantees that, if a program has at least one consistent answer set, any partial answer set returned will be a subset of some consistent answer set.