Une nouvelle sémantique pour la programmation logique capturant la sémantique des modèles stables : la sémantique des extensions

Abstract : Answer set programming is a well studied framework in logic programming. Many research works had been done in order to de ne a semantics for logic programs. Most of these semantics are iterated xed point semantics. The main idea is the canonical model approach which is a declarative semantics for logic programs that can be de ned by selecting for each program one of its canonical models. The notion of canonical models of a logic program is what it is called the stable models. The stable models of a logic program are in a certain sense the minimal Herbrand models of its "reduct" programs. Here we introduce a new semantics for logic programs that is di erent from the known xed point semantics. In our approach, logic programs are expressed as CNF formulas (sets of clauses) of a propositional logic for which we de ne a notion of extension. We prove in this semantics, that each consistent CNF formula admits at least an extension and for each given stable model of a logic program there exists an extension of its corresponding CNF formula which logically entails it. On the other hand, we show that some of the extensions do not entail any stable model, in this case, we de ne a simple descrimination condition which allows to recognize such extensions. These extensions could be very important, but are not captured by the stable models semantics. Our approach, extends the stable model semantics in this sense. Following the new semantics, we give a full characterization of the stable models of a logic program by means of the extensions of its CNF encoding verifying a simple condition, and provide a procedure which can be used to compute such extensions from which we deduce the stable models of the given logic program.
Document type :
Conference papers
Complete list of metadatas

Cited literature [15 references]  Display  Hide  Download

https://hal.inria.fr/hal-00829608
Contributor : Ist Inria Saclay <>
Submitted on : Monday, June 3, 2013 - 3:26:10 PM
Last modification on : Wednesday, September 12, 2018 - 1:26:29 AM
Long-term archiving on : Wednesday, September 4, 2013 - 4:13:54 AM

File

paper_31.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00829608, version 1

Collections

Citation

Belaïd Benhamou, Pierre Siegel. Une nouvelle sémantique pour la programmation logique capturant la sémantique des modèles stables : la sémantique des extensions. Huitièmes Journées Francophones de Programmation par Contraintes - JFPC 2012, May 2012, Toulouse, France. ⟨hal-00829608⟩

Share

Metrics

Record views

680

Files downloads

232