Negation by default and unstratifiable logic programs

AbstractThe default approach to the theory of logic programs (and deductive databases) is based on the interpretation of negation by default rules. Default logic is a well-suited formalism to express the Closed World Assumption and to define the declarative semantics of stratifiable logic programs. The case of disjunctive consequences in rules is treated. General logic programs may not have a meaning with respect to default semantics. The contribution of the paper is to exhibit an interesting class of programs having a default semantics, called effectively stratifiable programs. This time, disjunctive consequences are not considered. Effective stratification is a weaker constraint than stratification, local stratification and weak stratification. Besides enlarging the class of stratifiable logic programs, the paper contributes to provide a constructive definition of well-founded models of logic programs. The class of effectively stratifiable logic programs matches the class of programs having a total well-founded model and in general, the default semantics extends the well-founded semantics