Introduction to Bisimulation and Coinduction

A comprehensive treatment of two fundamental concepts in computer science, mathematics and other fields.

Davide Sangiorgi (Author)

9781107003637, Cambridge University Press

Hardback, published 13 October 2011

260 pages, 25 b/w illus. 210 exercises
25.4 x 17.8 x 1.8 cm, 0.64 kg

'Bisimulation and related coinductive techniques are now standard tools in many areas of computer science, but the lack of an accessible, comprehensive introduction has made it difficult for newcomers to appreciate their elegance and power. Here, at last, is that introduction - written by a world authority, weaving a multitude of previously disparate topics into a coherent narrative, and generously leavened with insightful exercises.' Benjamin C. Pierce, University of Pennsylvania

Induction is a pervasive tool in computer science and mathematics for defining objects and reasoning on them. Coinduction is the dual of induction and as such it brings in quite different tools. Today, it is widely used in computer science, but also in other fields, including artificial intelligence, cognitive science, mathematics, modal logics, philosophy and physics. The best known instance of coinduction is bisimulation, mainly employed to define and prove equalities among potentially infinite objects: processes, streams, non-well-founded sets, etc. This book presents bisimulation and coinduction: the fundamental concepts and techniques and the duality with induction. Each chapter contains exercises and selected solutions, enabling students to connect theory with practice. A special emphasis is placed on bisimulation as a behavioural equivalence for processes. Thus the book serves as an introduction to models for expressing processes (such as process calculi) and to the associated techniques of operational and algebraic analysis.

Preface
1. General introduction
2. Towards bisimulation
3. Coinduction and the duality with induction
4. Algebraic properties of bisimilarity
5. Processes with internal activities
6. Other approaches to behavioural equivalences
7. Refinements of simulation
8. Basic observables
Appendix A. Solutions to selected exercises
List of notations
Bibliography
Index.

Subject Areas: Programming & scripting languages: general [UMX], Information technology: general issues [UB], Mathematical logic [PBCD]