Program Correctness over Abstract Data Types, with Error State Semantics (Hardcover)

This research monograph is concerned with the theory of program specification and verification. More specifically, it is about proof systems, in the style of Floyd and Hoare, for proving the correctness of programs interpreted over abstract data types. In addition, the proof systems are designed to operate on programs with the semantic feature that using an uninitialised variable leads to an error message. Designed for the computer scientist, or mathematician interested in the theory of programming languages, the book discusses established and new tools necessary for proving the soundness and completeness of logics for partial and total correctness in an abstract setting. The new tools include classes of many-sorted structures, weak second order assertion languages, and, in particular, a full generalization of the theory of computable functions from the natural numbers to many-sorted abstract structures. Some new generalizations of the Church-Turing Thesis are discussed in detail.