Verification of sequential and concurrent programs

by Krzysztof R. Apt

Computer programs are becoming more and more part of systems that we rely on in our daily lives. The proper functioning and safety of these systems is of paramount importance. A major challenge for computer science is to develop methods that ensure program correctness. This textbook addresses this problem by providing a structured introduction to program verification. It uses one of the most common approaches, called the assertional method, because it relies on the use of assertions that are attached to program control points. Sequential programs in the form of deterministic and nondeterministic programs, and concurrent programs in the form of parallel and distributed programs are considered together with proof systems for the verification of their partial and total correctness. The use of these proof systems is demonstrated with the help of case studies. In particular, solutions to classical problems such as producer/consumer and mutual exclusion are formally verified. Each chapter is