Reducing Answer Set Programs under partial assignments

摘要

Given a propositional language, a partial assignment is of a pair of sets of atoms, (P, N) such that P and N are the sets of atoms that have been assigned true and false, respectively. Such partial assignments are of interest for many reasons. One is that they are the states explored by DPLL-based solvers for SAT and ASP (Answer Set Programming). In this paper, we consider ASP and study the problem of how to decide if a partial assignment can be extended to an answer set of a given logic program. For this, we propose a notion of reduction of a logic program under a partial assignment.