1977 · 16 citations · 4 references
ComputingComputer ScienceAlgorithmsFormal MethodsTheory Of ComputationDeductive VerificationFormal Language FoundationsSpecification LanguagesTermination AnalysisTheorem ProvingAbstract SemanticsAutomated Termination ProvingInitializationInvariant PreservationMapping FunctionsState Vector FormulationState Vector RepresentationTermination Proofs
A detailed look is taken at the problem of factoring program proofs into a proof of the underlying algorithm, followed by a proof of correct implementation of abstract variables at the concrete level. We do this considering four different concrete “marking” algorithms and formulating a single abstract algorithm and set of abstract specifications that can be instantiated to each of the four concrete cases. An intermediate assertion, as well as sufficient conditions for correct initialization, invariance, and correctness at termination are given at the abstract level. Proofs at the concrete level are then given by exhibiting appropriate mapping functions (from the concrete state vector to the abstract variables), and showing that the sufficient conditions are true. Proofs of termination are given by instantiating “termination schemas”.
4
The Art of Computer Programming
W.J. Worlton · Nuclear Science and Engineering · 1968 · 2.3K citations