Resource tableaux - (extended abstract)

Didier Galmiche, Daniel Mery, David Pym

Research output: Chapter in Book/Report/Conference proceedingChapter

13 Citations (Scopus)

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 for BI's tableaux to solve the resource-distribution problem, the labels being the elements of resource models. For BI with inconsistency, perpendicular to, 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, by considering partially defined monoids, a new semantics which generalizes the semantics of BI's pointer logic and for which BI is complete.
Original languageEnglish
Title of host publicationComputer Science Logic
Subtitle of host publication16th International Workshop, CSL 2002 11th Annual Conference of the EACSL Edinburgh, Scotland, UK, September 22–25 Proceedings
EditorsJ. Bradfield
Place of PublicationBerlin, Germany
PublisherSpringer
Pages183-199
Number of pages17
Volume2471
ISBN (Print)9783540442400
DOIs
Publication statusPublished - 2002
Event16th International Workshop, CSL 2002 11th Annual Conference of the EACSL - Edinburgh, UK United Kingdom
Duration: 22 Sep 200225 Sep 2002

Publication series

NameLecture Notes in Computer Science
Volume2471

Conference

Conference16th International Workshop, CSL 2002 11th Annual Conference of the EACSL
CountryUK United Kingdom
CityEdinburgh
Period22/09/0225/09/02

Keywords

  • tableaux
  • resources
  • decidability
  • semantics
  • finite model property
  • bi
  • logic

Fingerprint Dive into the research topics of 'Resource tableaux - (extended abstract)'. Together they form a unique fingerprint.

Cite this