Verification of Sequential and Concurrent Programs

This book provides a structured introduction to the verification of sequen­ tial and concurrent programs. It thus belongs to the area of programming languages but at the same time it is firmly based on mathematical logic. In logic one usually studies fixed syntactic or semantic objects. This is not necessarily the case in the area of program verification. The objects studied here, namely programs, do not have a standard syntax, their semantics can be defined in many different ways, and several approaches to their verification can be contemplated. These differences lead to various difficult design decisions. Even though we restrict our attention here to one programming style - imperative pro­ gramming - we are still confronted with a veritable cornucopia of pro­ gramming constructs from which an appropriate selection has to be made. Having studied some of these constructs separately does not yet imply that we understand their combined effect.

I In the Beginning.- 1 Introduction.- 2 Preliminaries.- II Sequential Programs.- 3 Deterministic Programs.- 4 Nondeterministic Programs.- III Parallel Programs.- 5 Disjoint Parallel Programs.- 6 Parallel Programs with Shared Variables.- 7 Parallel Programs with Synchronization.- IV Distributed Programs.- 8 Distributed Programs.- Appendices.- A Semantics.- B Axioms and Proof Rules.- C Proof Systems.- D Proof Outlines.- Author Index.- Symbol Index.