Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(7)
Classical Logic
Data Structure
intuitionistic logic
Modal Logic
Point of View
Weakest Precondition
Bunched Implications
Subscribe
Academic
Publications
BI as an assertion language for mutable data structures
BI as an assertion language for mutable data structures,10.1145/1988042.1988050,Sigplan Notices,Samin Ishtiaq,Peter W. O'Hearn
Edit
BI as an assertion language for mutable data structures
BibTex

RIS

RefWorks
Download
Samin Ishtiaq
,
Peter W. O'Hearn
Reynolds has developed a logic for reasoning about mutable data structures in which the pre and postconditions are written in an
intuitionistic logic
enriched with a spatial form of conjunction. We investigate the approach from the
point of view
of the logic BI of
bunched implications
of O'Hearn and Pym. We begin by giving a model in which the law of the excluded middle holds, thus showing that the approach is compatible with classical logic. The relationship between the intuitionistic and classical versions of the system is established by a translation, analogous to a translation from
intuitionistic logic
into the
modal logic
S4. We also consider the question of completeness of the axioms. BI's spatial implication is used to express weakest preconditions for objectcomponent assignments, and an axiom for allocating a cons cell is shown to be complete under an interpretation of triples that allows a command to be applied to states with dangling pointers. We make this latter a feature, by incorporating an operation, and axiom, for disposing of memory. Finally, we describe a local character enjoyed by specifications in the logic, and show how this enables a class of frame axioms, which say what parts of the heap don't change, to be inferred automatically.
Journal:
Sigplan Notices  SIGPLAN
, pp. 8496, 2011
DOI:
10.1145/1988042.1988050
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
portal.acm.org
)
(
dl.acm.org
)