Room P3.10, Mathematics Building

Luís Moniz Pereira, CENTRIA, Universidade Nova de Lisboa

Revised stable models – a new semantics for logic programs

Stable Models is a very well-known and frequently used semantics for logic programs. Furthermore, it is the basis for Answer-Set Programming (ASP) and its implementations. However, it suffers from a major problem, in that odd loops over default negation, such as $p \leftarrow \neg p$, can cause programs to have no semantics. This is because of impossibility of lending inconsistent support to conclusions. Another consequence is that Stable Models semantics is not relevant (in the sense that the truth of a literal may be found through a call-graph top-down derivation procedure), is not cummulative (which prevents it to enjoy tabling or memoizing), and is not subject to partial evaluation. This talk presents a new logic programming semantics, which I have dubbed Revised Stable Models. It includes Stable Models as a special case, and is relevant, cummulative, and partially evaluatable. The new semantics addresses the inconsistenty problem by employing a limited form of Reductio ad Absurdum. Moreover, two program transformations into normal logic programs are defined: one for enabling top down evaluation of literals; another for producing a normal program whose Stable Models are exactly the Revised Stable Models. This enables immediate implementation of the new semantics. A paper with the proposal will be sent beforehand to those so wishing.