Much current research in computer science is concerned with two questions: is a program correct? And how can we improve a correct program preserving correctness? This latter question is known as the refinement of programs and the purpose of this book is to consider these questions in a formal setting. In fact, correctness turns out to be a special case of refinement and so the focus is on refinement. Although a reasonable background knowledge is assumed from mathematics and CS, the book is a self-contained introduction suitable for graduate students and researchers coming to this subject for the first time. There are numerous exercises provided of varying degrees of challenge.
Author(s): Ralph-Johan Back, Joakim von Wright
Series: Graduate Texts in Computer Science
Publisher: Springer
Year: 1998
Language: English
Pages: 513
City: New York
Tags: Theory of Computation
Front Matter....Pages i-xv
Introduction....Pages 1-25
Front Matter....Pages 27-27
Posets, Lattices, and Categories....Pages 29-55
Higher-Order Logic....Pages 57-67
Functions....Pages 69-84
States and State Transformers....Pages 85-108
Truth Values....Pages 109-125
Predicates and Sets....Pages 127-138
Boolean Expressions and Conditionals....Pages 139-149
Relations....Pages 151-165
Types and Data Structures....Pages 167-183
Front Matter....Pages 185-185
Predicate Transformers....Pages 187-202
The Refinement Calculus Hierarchy....Pages 203-212
Statements....Pages 213-231
Statements as Games....Pages 233-247
Choice Semantics....Pages 249-257
Subclasses of Statements....Pages 259-267
Correctness and Refinement of Statements....Pages 269-298
Front Matter....Pages 299-299
Well-founded Sets and Ordinals....Pages 301-316
Fixed Points....Pages 317-327
Recursion....Pages 329-345
Front Matter....Pages 299-299
Iteration and Loops....Pages 347-363
Continuity and Executable Statements....Pages 365-382
Working with Arrays....Pages 383-402
The N-Queens Problem....Pages 403-412
Loops and Two-Person Games....Pages 413-423
Front Matter....Pages 425-425
Statement Classes and Normal Forms....Pages 427-445
Specification Statements....Pages 447-462
Refinement in Context....Pages 463-478
Iteration of Conjunctive Statements....Pages 479-496
Back Matter....Pages 497-519
