Book contents
- Frontmatter
- Contents
- List of illustrations
- Preface
- General introduction
- 1 Towards bisimulation
- 2 Coinduction and the duality with induction
- 3 Algebraic properties of bisimilarity
- 4 Processes with internal activities
- 5 Other approaches to behavioural equivalences
- 6 Refinements of simulation
- 7 Basic observables
- Appendix A Solutions to selected exercises
- List of notation
- References
- Index
General introduction
Published online by Cambridge University Press: 05 August 2012
- Frontmatter
- Contents
- List of illustrations
- Preface
- General introduction
- 1 Towards bisimulation
- 2 Coinduction and the duality with induction
- 3 Algebraic properties of bisimilarity
- 4 Processes with internal activities
- 5 Other approaches to behavioural equivalences
- 6 Refinements of simulation
- 7 Basic observables
- Appendix A Solutions to selected exercises
- List of notation
- References
- Index
Summary
Why bisimulation and coinduction
Induction is a pervasive tool in Computer Science and Mathematics for defining objects and proving properties of them. Coinduction is less known. It has been discovered and studied only in recent years. It is therefore not part of the standard scientific culture. The interest in coinduction is, however, growing: more and more application areas are suggested, and with compelling evidence.
Coinduction brings in tools for defining and reasoning on objects that are new and quite different from the tools provided by induction. This is because coinduction is the dual of induction. Induction has to do with least fixed points, coinduction with greatest fixed points. Greatest fixed points are as natural as least fixed points; in the same way coinduction is as natural as induction.
In the world of induction, constructions are stratified. Objects are hereditarily constructed, starting from basic atoms or primitive objects at the bottom, and then iteratively moving upward through higher or composite objects. Coinduction liberates us from the constraints of stratification. An immediate consequence is that the objects can be circular; more generally, they can be infinite. Examples of infinite structures are streams, as infinite sequences of elements, and real numbers, as infinite digit streams or Cauchy sequences. Another example is a process that continuously accepts interactions with the environment: semantically it is an infinite object, as it can engage in an infinite number of interactions.
- Type
- Chapter
- Information
- Introduction to Bisimulation and Coinduction , pp. 1 - 10Publisher: Cambridge University PressPrint publication year: 2011