Advanced Topics in Bisimulation and

Coinduction is a method for specifying and reasoning about infinite data types and automata with infinite behaviour. In recent years, it has come to play an ever more important role in the theory of computing. It is studied in many disciplines, including process theory and concurrency, modal logic and automata theory. Typically, coinductive proofs demonstrate the equivalence of two objects by constructing a suitable bisimulation relation between them. This collection of surveys is aimed at both researchers and Master's students in computer science and mathematics and deals with various aspects of bisimulation and coinduction, with an emphasis on process theory. Seven chapters cover the following topics: history, algebra and coalgebra, algorithmics, logic, higher-order languages, enhancements of the bisimulation proof method, and probabilities. Exercises are also included to help the reader master new material.

List of contributors	p. viii
Preface	p. xi
Origins of bisimulation and coinduction	p. 1
Introduction	p. 1
Bisimulation in modal logic	p. 3
Bisimulation in computer science	p. 7
Set theory	p. 15
The introduction of fixed points in computer science	p. 26
Fixed-point theorems	p. 29
Bibliography	p. 31
An introduction to (co)algebra and (co)induction	p. 38
Introduction	p. 38
Algebraic and coalgebraic phenomena	p. 42
Inductive and coinductive definitions	p. 47
Functoriality of products, coproducts and powersets	p. 50
Algebras and induction	p. 53
Coalgebras and coinduction	p. 66
Proofs by coinduction and bisimulation	p. 76
Processes coalgebraically	p. 79
Trace semantics, coalgebraically	p. 87
Exercises	p. 90
Bibliography	p. 94
The algorithmics of bisimilarity	p. 100
Introduction	p. 100
Classical algorithms for bisimilarity	p. 102
The complexity of checking bisimilarity over finite processes	p. 122
Decidability results for bisimilarity over infinite-state systems	p. 142
The use of bisimilarity checking in verification and tools	p. 157
Bibliography	p. 163
Bisimulation and logic	p. 173
Introduction	p. 173
Modal logic and bisimilarity	p. 175
Bisimulation invariance	p. 179
Modal mu-calculus	p. 184
Monadic second-order logic and bisimulation invariance	p. 190
Bibliography	p. 195
Howe's method for higher-order languages	p. 197
Introduction	p. 197
Call-by-value ¿-calculus	p. 200
Applicative (bi)similarity for call-by-value ¿-calculus	p. 201
Congruence	p. 204
Howe's construction	p. 207
Contextual equivalence	p. 210
The transitive closure trick.	p. 214
CIU-equivalence	p. 218
Call-by-name equivalences	p. 225
Summary	p. 229
Assessment	p. 229
Bibliography	p. 230
Enhancements of the bisimulation proof method	p. 233
The need for enhancements	p. 235
Examples of enhancements	p. 239
A theory of enhancements	p. 249
Congruence and up to context techniques	p. 260
The case of weak bisimilarity	p. 269
A summary of up-to techniques for bisimulation	p. 286
Bibliography	p. 287
Probabilistic bisimulation	p. 290
Introduction	p. 290
Discrete systems	p. 295
A rapid survey of measure theory	p. 300
Labelled Markov processes	p. 306
Giry's monad	p. 308
Probabilistic bisimulation	p. 310
Logical characterisation	p. 313
Probabilistic cocongruences	p. 316
Kozen's coinduction principle	p. 319
Conclusions	p. 321
Bibliography	p. 323
Table of Contents provided by Ingram. All Rights Reserved.

What is included with this book?

The New copy of this book will include any supplemental materials advertised. Please check the title of the book to determine if it should include any access cards, study guides, lab manuals, CDs, etc.

The Used, Rental and eBook copies of this book are not guaranteed to include any supplemental materials. Typically, only the book itself is included. This is true even if the title states it includes any access cards, study guides, lab manuals, CDs, etc.

FREE SHIPPING

Rent More, Save More! Use code: BBRENTAL

5% off 1 book, 7% off 2 books, 10% off 3+ books

Advanced Topics in Bisimulation and Coinduction

Summary

Table of Contents

Supplemental Materials