a characterization of hoare's logic for programs with pascal-like procedures
This paper presents a new characterization of applicability and limitations of Hoare's logic. We consider a programming language L Pas consisting of nondeterministic programs with a Pascal-like procedure concept and prove as our main theorem: Admissible sublanguages L of L Pas have a sound and relatively complete Hoare logic if and only if all programs in L have regular formal call trees. Moreover, we present an explicit Hoare calculus for L whenever such a Hoare logic exists. Our theorem generalizes Clarke's results on completeness and incompleteness for languages with procedures [Cl 79] and improves Lipton's characterization of Hoare's logic which cannot deal with nondeterminism and does not provide explicit calculi [Li 77].
characterization logic program procedure paper applications programming language language nondeterminism concept sound completeness hoare logic formalism trees