Fages’ theorem and answer set programming

Email fyuliyaesravlgcs utexas edu We generalize a theorem by Francois Fages that de scribes the relationship between the completion seman tics and the answer set semantics for logic programs with negation as failure The study of this relationship is important in connection with the emergence of an swer set programming Whenever the two semantics are equivalent answer sets can be computed by a sat isability solver and the use of answer set solvers such as smodels and dlv is unnecessary A logic program ming representation of the blocks world due to Ilkka Niemela is discussed as an exampl