article · 2008
Recursive Assertions for Data Structures
Cited by 0Abstract and details only
Abstract
We present an assertion language for expressing properties of data structures. Its key features are constraints over arrays, multisets and integers which allow the specification of basic assertions, and rules, which allow the recursive specification of assertions. This language can thus be used to define assertions to an arbitrary level of expressiveness, ranging from low-level properties of memory allocation, for example, to abstract properties of complex data structures such as AVL trees. The main result is a proof method for verification conditions arising from a program annotated with assertions. The method has two main components. First and foremost is an unfolding algorithm which works by reducing the recursive definitions so that a constraint proof may now be applied. Here we introduce a notion of coinduction which forms the basis for termination of the unfolding process. The second step is to reduce the constraints, which in general contain expressions involving all the three data types of integers, arrays and multisets, into a base constraint involving only integer constraints. Base constraints can then be dispensed with available solvers. We finally show via a small benchmark of classic examples that our proof method is practical. 1.
Cite this paper
(2008). Recursive Assertions for Data Structures.
“Recursive Assertions for Data Structures.” 2008.
2008. “Recursive Assertions for Data Structures.”
(2008) ‘Recursive Assertions for Data Structures’.
@article{anon2008recursive,
title = {{Recursive Assertions for Data Structures}},
year = {2008}
}Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.