Research

Resource tableaux - (extended abstract)


Reference:

Galmiche, D., Mery, D. and Pym, D., 2002. Resource tableaux - (extended abstract). Lecture Notes in Computer Science, 2471, pp. 183-199.

Related documents:

This repository does not currently have the full-text of this item.
You may be able to access a copy if URLs are provided below.

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.

Details

Item Type Articles
CreatorsGalmiche, D., Mery, D. and Pym, D.
Uncontrolled Keywordstableaux, resources, decidability, semantics, finite model property, bi, logic
DepartmentsFaculty of Science > Biology & Biochemistry
RefereedYes
StatusPublished
ID Code4228
Additional InformationID number: ISI:000187294300013

Export

Actions (login required)

View Item