zbMATH — the first resource for mathematics

Automatic verification of parameterized data structures. (English) Zbl 1180.68126
Hermanns, Holger (ed.) et al., Tools and algorithms for the construction and analysis of systems. 12th international conference, TACAS 2006, held as part of the joint European conferences on theory and practice of software, ETAPS 2006, Vienna, Austria, March 25 – April 2, 2006. Proceedings. Berlin: Springer (ISBN 3-540-33056-9/pbk). Lecture Notes in Computer Science 3920, 27-41 (2006).
Summary: Verifying correctness of programs operating on data structures has become an integral part of software verification. A method is a program that acts on an input data structure (modeled as a graph) and produces an output data structure. The parameterized correctness problem for such methods can be defined as follows: Given a method and a property of the input graphs, we wish to verify that for all input graphs, parameterized by their size, the output graphs also satisfy the property. We present an automated approach to verify that a given method preserves a given property for a large class of methods. Examples include reversals of linked lists, insertion, deletion and iterative modification of nodes in directed graphs. Our approach draws on machinery from automata theory and temporal logic. For a useful class of data structures and properties, our solution is polynomial in the size of the method and size of the property specification.
For the entire collection see [Zbl 1103.68005].

68P05 Data structures
68Q60 Specification and verification (program logics, model checking, etc.)
Full Text: DOI