Resource Tableaux (extended abstract)

Didier Galmiche 1 Daniel Méry 1 David Pym
1 TYPES - Logic, proof Theory and Programming
LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
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.
Type de document :
Communication dans un congrès
J.C. Bradfield. 16th International Workshop on Computer Science Logic - CSL' 2002, 2002, Edinburgh, Scotland, UK, Springer Verlag, 2471, pp.183-199, 2002, Lecture Notes in Computer Science
Liste complète des métadonnées

https://hal.inria.fr/inria-00100798
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 14:51:06
Dernière modification le : mardi 24 avril 2018 - 13:36:37

Identifiants

  • HAL Id : inria-00100798, version 1

Collections

Citation

Didier Galmiche, Daniel Méry, David Pym. Resource Tableaux (extended abstract). J.C. Bradfield. 16th International Workshop on Computer Science Logic - CSL' 2002, 2002, Edinburgh, Scotland, UK, Springer Verlag, 2471, pp.183-199, 2002, Lecture Notes in Computer Science. 〈inria-00100798〉

Partager

Métriques

Consultations de la notice

109