ITERATIVE BELIEF REVISION IN EXTENDED LOGIC PROGRAMMING

Extended logic programming augments conventional logic programming wit h both default and explicit negation. Several semantics for extended l ogic programs have been proposed that extend the well-founded semantic s for logic programs with default negation (called normal programs). W e show that two of these extended semantics are intractable; both Dung 's grounded argumentation semantics and the well-founded semantics of Alferes et al. are NP-hard. Nevertheless, we also show that these two semantics have a common core, a more restricted form of the grounded s emantics, which is tractable and can be computed iteratively in quadra tic time. Moreover, this semantics is a representative of a rich class of tractable semantics based on a notion of iterative belief revision .