Accession Number : ADA116035

Title :   Verification of Concurrent Programs. Part II. Temporal Proof Principles.

Descriptive Note : Technical rept.,

Corporate Author : STANFORD UNIV CA DEPT OF COMPUTER SCIENCE

Personal Author(s) : Manna,Zohar ; Pnueli,Amir

PDF Url : ADA116035

Report Date : Sep 1981

Pagination or Media Count : 53

Abstract : In this paper, the second of a series on the application of temporal logic to concurrent programs, we present proof methods for establishing invariance (safety) and eventuality (liveness) properties. The proof principle for establishing invariance properties is based on computational induction, and is a generalization of the inductive assertion method. For a restricted class of concurrent programs we present an algorithm for the automatic derivation of invariant assertions. In order to establish eventuality properties we present several proof principles that translate the structure of the program into basic temporal statements about its behavior. These principles can be viewed as providing the temporal semantics of the program. The basic statements thus derived are then combined into temporal proofs for the establishment of eventuality properties.

Descriptors :   *Applied mathematics, *Computer logic, *Multiprocessors, Dual mode, Invariance, Multimode, Algorithms, Semantics, Computations

Subject Categories : Theoretical Mathematics
      Computer Hardware

Distribution Statement : APPROVED FOR PUBLIC RELEASE