The semantics of BI and resource tableaux

D Galmiche, D Mery, D Pym

Research output: Contribution to journalArticle

53 Citations (Scopus)

Abstract

The logic of bunched implications, BI, provides a logical analysis of a basic notion of resource that is rich enough, for example, to form the logical basis for 'pointer logic' and,separation logic' semantics for programs that 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. Then, from these results, we can define a new resource semantics of BI, based on partially defined monoids, and prove that this semantics is complete. Such a semantics, based on partiality, is closely related to the semantics of BI's (intuitionistic) pointer and separation logics. Returning to the tableaux calculus, we propose a new version with liberalised rules for which the countermodels are closely related to the topological Kripke semantics of BI. As consequences of the relationships between semantics of BI and resource tableaux, we prove two new strong results for propositional BI: its decidability and the finite model property with respect to topological semantics.
Original languageEnglish
Pages (from-to)1033-1088
Number of pages56
JournalMathematical Structures in Computer Science
Volume15
Issue number6
DOIs
Publication statusPublished - 2005

Fingerprint

Tableaux
Semantics
Resources
Separation Logic
Labels
Logic
Kripke Semantics
Proof Search
Dependency Graph
Finite Models
Theorem proving
Intuitionistic Logic
Computability and decidability
Theorem Proving
Monoids
Soundness
Decidability
Search Methods
Inconsistency
Perpendicular

Cite this

The semantics of BI and resource tableaux. / Galmiche, D; Mery, D; Pym, D.

In: Mathematical Structures in Computer Science, Vol. 15, No. 6, 2005, p. 1033-1088.

Research output: Contribution to journalArticle

Galmiche, D ; Mery, D ; Pym, D. / The semantics of BI and resource tableaux. In: Mathematical Structures in Computer Science. 2005 ; Vol. 15, No. 6. pp. 1033-1088.
@article{a78538ca06db433cab5c5fe9b1f03d70,
title = "The semantics of BI and resource tableaux",
abstract = "The logic of bunched implications, BI, provides a logical analysis of a basic notion of resource that is rich enough, for example, to form the logical basis for 'pointer logic' and,separation logic' semantics for programs that 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. Then, from these results, we can define a new resource semantics of BI, based on partially defined monoids, and prove that this semantics is complete. Such a semantics, based on partiality, is closely related to the semantics of BI's (intuitionistic) pointer and separation logics. Returning to the tableaux calculus, we propose a new version with liberalised rules for which the countermodels are closely related to the topological Kripke semantics of BI. As consequences of the relationships between semantics of BI and resource tableaux, we prove two new strong results for propositional BI: its decidability and the finite model property with respect to topological semantics.",
author = "D Galmiche and D Mery and D Pym",
note = "ID number: ISI:000234499600002",
year = "2005",
doi = "10.1017/s0960129505004858",
language = "English",
volume = "15",
pages = "1033--1088",
journal = "Mathematical Structures in Computer Science",
issn = "0960-1295",
publisher = "Cambridge University Press",
number = "6",

}

TY - JOUR

T1 - The semantics of BI and resource tableaux

AU - Galmiche, D

AU - Mery, D

AU - Pym, D

N1 - ID number: ISI:000234499600002

PY - 2005

Y1 - 2005

N2 - The logic of bunched implications, BI, provides a logical analysis of a basic notion of resource that is rich enough, for example, to form the logical basis for 'pointer logic' and,separation logic' semantics for programs that 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. Then, from these results, we can define a new resource semantics of BI, based on partially defined monoids, and prove that this semantics is complete. Such a semantics, based on partiality, is closely related to the semantics of BI's (intuitionistic) pointer and separation logics. Returning to the tableaux calculus, we propose a new version with liberalised rules for which the countermodels are closely related to the topological Kripke semantics of BI. As consequences of the relationships between semantics of BI and resource tableaux, we prove two new strong results for propositional BI: its decidability and the finite model property with respect to topological semantics.

AB - The logic of bunched implications, BI, provides a logical analysis of a basic notion of resource that is rich enough, for example, to form the logical basis for 'pointer logic' and,separation logic' semantics for programs that 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. Then, from these results, we can define a new resource semantics of BI, based on partially defined monoids, and prove that this semantics is complete. Such a semantics, based on partiality, is closely related to the semantics of BI's (intuitionistic) pointer and separation logics. Returning to the tableaux calculus, we propose a new version with liberalised rules for which the countermodels are closely related to the topological Kripke semantics of BI. As consequences of the relationships between semantics of BI and resource tableaux, we prove two new strong results for propositional BI: its decidability and the finite model property with respect to topological semantics.

U2 - 10.1017/s0960129505004858

DO - 10.1017/s0960129505004858

M3 - Article

VL - 15

SP - 1033

EP - 1088

JO - Mathematical Structures in Computer Science

JF - Mathematical Structures in Computer Science

SN - 0960-1295

IS - 6

ER -