Computability and Complexity Results for a Spatial Assertion Language for Data Structures
The work
| Authors | Cristiano Calcagno; Hongseok Yang; Peter W. O'Hearn |
|---|---|
| Editors | |
| Type | incollection |
| Year | 2001 |
| Citekey | calcagno2001computability |
Where it appeared
| Published in | Foundations of Software Technology and Theoretical Computer Science (FSTTCS) |
|---|---|
| Publisher | Springer |
| Volume | 2245 |
| Pages | 108--119 |
Identifiers
| DOI | 10.1007/3-540-45294-x_10 |
|---|
Abstract
This paper studies a recently developed an approach to rea- soning about mutable data structures, which uses an assertion language with spatial conjunction and implication connectives. We investigate computability and complexity properties of a subset of the language, which allows statements about the shape of pointer structures (such as “there is a link from x to y”) to be made, but not statements about the data held in cells (such as “x is a prime number”). We show that valid- ity, even for this restricted language, is not r.e., but that the quantifier- free sublanguage is decidable. We then consider the complexity of model checking and validity for several fragments.
A copy is held
pdf, 180.0 kB. Not published — it may be under copyright. The facts and links here are.
How it got here
| How it got here | agent via bibtex |
|---|---|
| Added | 2026-08-05 00:00 UTC |
| Approved by | a person 2026-08-14 11:37 UTC |
Filed under
Cite it as
@incollection{calcagno2001computability,
title = {Computability and Complexity Results for a Spatial Assertion Language for Data Structures},
author = {Cristiano Calcagno and Hongseok Yang and Peter W. O'Hearn},
year = {2001},
booktitle = {Foundations of Software Technology and Theoretical Computer Science (FSTTCS)},
publisher = {Springer},
volume = {2245},
pages = {108--119},
doi = {10.1007/3-540-45294-x_10},
}
This record lives at https://refs.drheap.org/calcagno2001computability/ and will keep doing so.