Some classes of naturally provable programs
Lists
Only you see this
Abstract
Three different classes of programs are identified for which the proof of correctness is shown to be “natural”, in that the functional input-output specifications of the programs lead, in a straightforward manner, to the verification conditions that should be proven. Furthermore, these verification conditions are shown to be necessary and sufficient so that a proof/refutation follows by proving/disproving the corresponding verification conditions. It is not necessary to follow the exact control flow of the programs to generate these conditions; certain simple checks are enough to show whether a particular program belongs to one of the classes. These apparently different programs have the common feature that they operate “uniformly” on the data domain; changing the input to the program changes the dynamic behavior of the program in a predictable, easily definable fashion. Implications of this feature in program construction are discussed.
BibTeX
@inproceedings{basu1976some,
author = {Soumya Basu and Jayadev Misra},
title = {{Some classes of naturally provable programs}},
booktitle = {International Conference on Software Engineering},
year = {1976},
doi = {10.5555/800253.807711},
}Loading related content...