Proving Properties of Complex Data Structures
Ben Wegbreit, Jay M. Spitzen · Journal of the ACM · 1976
This paper is concerned with proving properties of programs which use data structures. The goal is to be able to prove that all instances of a class (e.g. as defined in Simula) satisfy some property. A method of proof which achieves this goal, generator induction , is studied and compared to other proof rules and methods: inductive assertions, recursion induction, computation induction, and, in some detail, structural induction. The paper concludes by using generator induction to prove a characteristic property of an implementation of hashtables.