Resource Tableaux (extended abstract)
Identifieur interne : 008578 ( Main/Merge ); précédent : 008577; suivant : 008579Resource Tableaux (extended abstract)
Auteurs : Didier Galmiche ; Daniel Mery ; David PymSource :
English descriptors
- KwdEn :
Abstract
The logic of bunched implications BI provides a logical analysis of a basic notion of resource rich enough to provide a ``pointer logic'' semantics for programs which manipulate mutable data structures. We develop a theory of semantic tableaux for BI, so providing an elegant basis for efficient theorem proving tools for BI. It is based on the use of an algebra of labels to solve the resource-distribution problem, the labels being the elements of resource models. For BI with inconsistency, the challenge consists in dealing with BI's Grothendieck topological models within such a proof-search method, based on labels. We prove soundness and completeness theorems for a resource tableaux method TBI with respect to this semantics and provide a way to build countermodels from so-called dependency graphs. As consequences, we have two strong new results for BI : the decidability of propositional BI and the finite model property with respect to Grothendieck topological semantics. In addition, we propose a new semantics which generalizes the semantics of BI's pointer logic and for which BI is complete.
Links toward previous steps (curation, corpus...)
- to stream Crin, to step Corpus: 003321
- to stream Crin, to step Curation: 003321
- to stream Crin, to step Checkpoint: 000E17
Links to Exploration step
CRIN:galmiche02cLe document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="fr" wicri:score="-80">Resource Tableaux (extended abstract)</title></titleStmt><publicationStmt><idno type="RBID">CRIN:galmiche02c</idno><date when="2002" year="2002">2002</date><idno type="wicri:Area/Crin/Corpus">003321</idno><idno type="wicri:Area/Crin/Curation">003321</idno><idno type="wicri:explorRef" wicri:stream="Crin" wicri:step="Curation">003321</idno><idno type="wicri:Area/Crin/Checkpoint">000E17</idno><idno type="wicri:explorRef" wicri:stream="Crin" wicri:step="Checkpoint">000E17</idno><idno type="wicri:Area/Main/Merge">008578</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="fr">Resource Tableaux (extended abstract)</title><author><name sortKey="Galmiche, Didier" sort="Galmiche, Didier" uniqKey="Galmiche D" first="Didier" last="Galmiche">Didier Galmiche</name></author><author><name sortKey="Mery, Daniel" sort="Mery, Daniel" uniqKey="Mery D" first="Daniel" last="Mery">Daniel Mery</name></author><author><name sortKey="Pym, David" sort="Pym, David" uniqKey="Pym D" first="David" last="Pym">David Pym</name></author></analytic></biblStruct></sourceDesc></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>decidability</term><term>finite model property</term><term>resources</term><term>semantics</term><term>tableaux</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en" wicri:score="2644">The logic of bunched implications BI provides a logical analysis of a basic notion of resource rich enough to provide a ``pointer logic'' semantics for programs which manipulate mutable data structures. We develop a theory of semantic tableaux for BI, so providing an elegant basis for efficient theorem proving tools for BI. It is based on the use of an algebra of labels to solve the resource-distribution problem, the labels being the elements of resource models. For BI with inconsistency, the challenge consists in dealing with BI's Grothendieck topological models within such a proof-search method, based on labels. We prove soundness and completeness theorems for a resource tableaux method TBI with respect to this semantics and provide a way to build countermodels from so-called dependency graphs. As consequences, we have two strong new results for BI : the decidability of propositional BI and the finite model property with respect to Grothendieck topological semantics. In addition, we propose a new semantics which generalizes the semantics of BI's pointer logic and for which BI is complete.</div></front></TEI></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Merge
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 008578 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Merge/biblio.hfd -nk 008578 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Main
|étape= Merge
|type= RBID
|clé= CRIN:galmiche02c
|texte= Resource Tableaux (extended abstract)
}}
| This area was generated with Dilib version V0.6.33. |  |