VAL@SAIL.STANFORD.EDU (Vladimir Lifschitz) (11/17/86)
Commonsense and Non-Monotonic Reasoning Seminar LOGIC PROGRAMMING AND CIRCUMSCRIPTION Vladimir Lifschitz Thursday, November 20, 4pm MJH 252 The talk will be based on my paper "On the declarative semantics of logic programs with negation". A few copies of the paper are available in my office, MJH 362. ABSTRACT. A logic program can be viewed as a predicate formula, and its declarative meaning can be defined by specifying a certain Herbrand model of that formula. For programs without negation, this model is defined either as the Herbrand model with the minimal set of positive ground atoms, or, equivalently, as the minimal fixed point of a certain operator associated with the formula (Van Emden and Kowalski). These solutions do not apply to general logic programs, because a program with negation may have many minimal Herbrand models, and the corresponding operator may have many minimal fixed points. Apt, Blair and Walker and, independently, Van Gelder, introduced a class of general logic programs which disallow certain combinations of recursion and negation, and showed how to use the fixed point approach to define a declarative semantics for such programs. Using the concept of circumscription, we extend the minimal model approach to stratified programs and show that it leads to the same semantics.