A new fixpoint semantics for general logic programs compared with the well-founded and the stable model semantics
Identifieur interne : 00DA92 ( Main/Exploration ); précédent : 00DA91; suivant : 00DA93A new fixpoint semantics for general logic programs compared with the well-founded and the stable model semantics
Auteurs : François Fages [France]Source :
- New Generation Computing [ 0288-3635 ] ; 1991-08-01.
English descriptors
- KwdEn :
- Teeft :
- Artificial intelligence, Base case, Best strategy, Canonical model, Complete interpreter, Complete semilattice, Database, Declarative semantics, Deductive databases, Expert systems, Fages, Fair strategy, Finitely converges, Fixpoint, Fixpoint semantics, General logic program, General logic programs, Herbrand, Herbrand interpretation, Justification maintenance operator, Limit ordinal, Logic, Logic program, Logic programming, Logic programs, Loop checks, Model semantics, Morgan kaufmann, Naive interpreter, Ordinal, Ordinal power, Ordinal powers, Other hand, Partial interpretation, Partial model, Proc, Programming, Rational model, Rational model semantics, Rule instance, Semantics, Stable model, Stable model semantics, Stable models, Time complexity, Transfinite, Transfinite induction, Truth maintenance system, Truth maintenance systems, Unfounded sets.
Abstract
Abstract: We study a new fixpoint semantics for logic programs with negation. Our construction is intermediate between Van Gelder’s well-founded model and Gelfond and Lifschitz’s stable model semantics. We show first that the stable models of a logic programP are exactly the well-supported models ofP, i.e. the supported models with loop-free finite justifications. Then we associate to any logic programP a non-monotonic operator over the semilattice of justified interpretations, and we define in an abstract form its ordinal powers. We show that the fixpoints of this operator are the stable models ofP, and that its ordinal powers after some ordinala are extensions of the well-founded partial model ofP. In particular ifP has a well-founded model then that canonical model is also an ordinal power and the unique fixpoint of our operator. We show with examples of logic programs which have a unique stable model but no well-founded model that the converse is false. We relate also our work to Doyle’s truth maintenance system and some implementations of rule-based expert systems.
Url:
DOI: 10.1007/BF03037172
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 001105
- to stream Istex, to step Curation: 001089
- to stream Istex, to step Checkpoint: 003159
- to stream Main, to step Merge: 00E370
- to stream Main, to step Curation: 00DA92
Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">A new fixpoint semantics for general logic programs compared with the well-founded and the stable model semantics</title><author><name sortKey="Fages, Francois" sort="Fages, Francois" uniqKey="Fages F" first="François" last="Fages">François Fages</name></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:485EB37C576040F71432C3D4182D38519EDC85D7</idno><date when="1991" year="1991">1991</date><idno type="doi">10.1007/BF03037172</idno><idno type="url">https://api.istex.fr/ark:/67375/1BB-R8W4G90R-J/fulltext.pdf</idno><idno type="wicri:Area/Istex/Corpus">001105</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">001105</idno><idno type="wicri:Area/Istex/Curation">001089</idno><idno type="wicri:Area/Istex/Checkpoint">003159</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">003159</idno><idno type="wicri:doubleKey">0288-3635:1991:Fages F:a:new:fixpoint</idno><idno type="wicri:Area/Main/Merge">00E370</idno><idno type="wicri:Area/Main/Curation">00DA92</idno><idno type="wicri:Area/Main/Exploration">00DA92</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">A new fixpoint semantics for general logic programs compared with the well-founded and the stable model semantics</title><author><name sortKey="Fages, Francois" sort="Fages, Francois" uniqKey="Fages F" first="François" last="Fages">François Fages</name><affiliation wicri:level="3"><country xml:lang="fr">France</country><wicri:regionArea>Ecole Normale Supérieure, LCR Thomson-CSF and LIENS, URA CNRS, 45 rue d’Ulm, 75005, Paris</wicri:regionArea><placeName><region type="region" nuts="2">Île-de-France</region><settlement type="city">Paris</settlement></placeName></affiliation></author></analytic><monogr></monogr><series><title level="j">New Generation Computing</title><title level="j" type="abbrev">New Gener Comput</title><idno type="ISSN">0288-3635</idno><idno type="eISSN">1882-7055</idno><imprint><publisher>Springer-Verlag</publisher><pubPlace>Tokyo</pubPlace><date type="published" when="1991-08-01">1991-08-01</date><biblScope unit="volume">9</biblScope><biblScope unit="issue">3-4</biblScope><biblScope unit="page" from="425">425</biblScope><biblScope unit="page" to="443">443</biblScope></imprint><idno type="ISSN">0288-3635</idno></series></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0288-3635</idno></seriesStmt></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Negation</term><term>Non-monotonic Induction</term><term>Stable Models</term><term>Truth Maintenance Systems</term></keywords><keywords scheme="Teeft" xml:lang="en"><term>Artificial intelligence</term><term>Base case</term><term>Best strategy</term><term>Canonical model</term><term>Complete interpreter</term><term>Complete semilattice</term><term>Database</term><term>Declarative semantics</term><term>Deductive databases</term><term>Expert systems</term><term>Fages</term><term>Fair strategy</term><term>Finitely converges</term><term>Fixpoint</term><term>Fixpoint semantics</term><term>General logic program</term><term>General logic programs</term><term>Herbrand</term><term>Herbrand interpretation</term><term>Justification maintenance operator</term><term>Limit ordinal</term><term>Logic</term><term>Logic program</term><term>Logic programming</term><term>Logic programs</term><term>Loop checks</term><term>Model semantics</term><term>Morgan kaufmann</term><term>Naive interpreter</term><term>Ordinal</term><term>Ordinal power</term><term>Ordinal powers</term><term>Other hand</term><term>Partial interpretation</term><term>Partial model</term><term>Proc</term><term>Programming</term><term>Rational model</term><term>Rational model semantics</term><term>Rule instance</term><term>Semantics</term><term>Stable model</term><term>Stable model semantics</term><term>Stable models</term><term>Time complexity</term><term>Transfinite</term><term>Transfinite induction</term><term>Truth maintenance system</term><term>Truth maintenance systems</term><term>Unfounded sets</term></keywords></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: We study a new fixpoint semantics for logic programs with negation. Our construction is intermediate between Van Gelder’s well-founded model and Gelfond and Lifschitz’s stable model semantics. We show first that the stable models of a logic programP are exactly the well-supported models ofP, i.e. the supported models with loop-free finite justifications. Then we associate to any logic programP a non-monotonic operator over the semilattice of justified interpretations, and we define in an abstract form its ordinal powers. We show that the fixpoints of this operator are the stable models ofP, and that its ordinal powers after some ordinala are extensions of the well-founded partial model ofP. In particular ifP has a well-founded model then that canonical model is also an ordinal power and the unique fixpoint of our operator. We show with examples of logic programs which have a unique stable model but no well-founded model that the converse is false. We relate also our work to Doyle’s truth maintenance system and some implementations of rule-based expert systems.</div></front></TEI><affiliations><list><country><li>France</li></country><region><li>Île-de-France</li></region><settlement><li>Paris</li></settlement></list><tree><country name="France"><region name="Île-de-France"><name sortKey="Fages, Francois" sort="Fages, Francois" uniqKey="Fages F" first="François" last="Fages">François Fages</name></region></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 00DA92 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 00DA92 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Main
|étape= Exploration
|type= RBID
|clé= ISTEX:485EB37C576040F71432C3D4182D38519EDC85D7
|texte= A new fixpoint semantics for general logic programs compared with the well-founded and the stable model semantics
}}
| This area was generated with Dilib version V0.6.33. |  |