Advanced Topics in Bisimulation and Coinduction by Davide Sangiorgi, Jan Rutten

By Davide Sangiorgi, Jan Rutten

Coinduction is a technique for specifying and reasoning approximately endless info kinds and automata with endless behaviour. lately, it has come to play an ever extra very important position within the thought of computing. it really is studied in lots of disciplines, together with strategy idea and concurrency, modal common sense and automata thought. usually, coinductive proofs reveal the equivalence of 2 items through developing an appropriate bisimulation relation among them. This number of surveys is aimed toward either researchers and Master's scholars in machine technological know-how and arithmetic and bargains with a number of facets of bisimulation and coinduction, with an emphasis on strategy thought. Seven chapters disguise the subsequent themes: heritage, algebra and coalgebra, algorithmics, common sense, higher-order languages, improvements of the bisimulation facts procedure, and chances. routines also are integrated to aid the reader grasp new material.

Contents: 1. Origins of bisimulation and coinduction (Davide Sangiorgi) — 2. An advent to (co)algebra and (co)induction (Bart Jacobs and Jan Rutten) — three. The algorithmics of bisimilarity (Luca Aceto, Anna Ingolfsdottir and Jiří Srba) — four. Bisimulation and common sense (Colin Stirling) — five. Howe’s strategy for higher-order languages (Andrew Pitts) — 6. improvements of the bisimulation evidence process (Damien Pous and Davide Sangiorgi) — 7. Probabilistic bisimulation (Prakash Panangaden)

Show description

Read or Download Advanced Topics in Bisimulation and Coinduction PDF

Best machine theory books

Theory And Practice Of Uncertain Programming

Real-life judgements tend to be made within the country of uncertainty resembling randomness and fuzziness. How can we version optimization difficulties in doubtful environments? How can we clear up those versions? in an effort to solution those questions, this booklet presents a self-contained, complete and updated presentation of doubtful programming concept, together with a variety of modeling principles, hybrid clever algorithms, and functions in approach reliability layout, venture scheduling challenge, car routing challenge, facility place challenge, and computing device scheduling challenge.

Algebras in Genetics

The aim of those notes is to provide a slightly entire presentation of the mathematical idea of algebras in genetics and to debate intimately many functions to concrete genetic events. traditionally, the topic has its starting place in numerous papers of Etherington in 1939- 1941. primary contributions were given via Schafer, Gonshor, Holgate, Reiers¢l, Heuch, and Abraham.

Augmented Marked Graphs

Petri nets are a proper and theoretically wealthy version for the modelling and research of structures. A subclass of Petri nets, augmented marked graphs own a constitution that's in particular fascinating for the modelling and research of platforms with concurrent techniques and shared assets. This monograph involves 3 elements: half I offers the conceptual historical past for readers who've no past wisdom on Petri nets; half II elaborates the speculation of augmented marked graphs; eventually, half III discusses the applying to approach integration.

Large-Scale Scientific Computing: 9th International Conference, LSSC 2013, Sozopol, Bulgaria, June 3-7, 2013. Revised Selected Papers

This e-book constitutes the completely refereed post-conference court cases of the ninth foreign convention on Large-Scale medical Computations, LSSC 2013, held in Sozopol, Bulgaria, in June 2013. The seventy four revised complete papers awarded including five plenary and invited papers have been rigorously reviewed and chosen from a variety of submissions.

Extra resources for Advanced Topics in Bisimulation and Coinduction

Sample text

5 Peter Aczel In mathematics, bisimulation and non-well-founded sets are made popular by Peter Aczel, notably with his book [Acz88]. Aczel is looking for mathematical foundations of processes, prompted by the work of Milner on CCS and his way of equating processes with an infinite behaviour via a bisimulation quotient. Aczel reformulates Forti and Honsell’s anti-foundation axiom X1 . In Forti and 2 We use a notation different from Forti and Honsell here. Origins of bisimulation and coinduction 2 Ñ aaa Ñ aa Ñ aa ÑÑ 0 ÑÐ Ñ 0o 1 a c ÐÐ Ð ÐÐ Ð Ð 21  b Fig.

Principia Mathematica, 3 vols. Cambridge University Press, 1910, 1912, 1913. [San09] D. Sangiorgi. On the origins of bisimulation and coinduction. ACM Transactions on Programming Languages and Systems, 31(4), 2009. [San12] D. Sangiorgi. An Introduction to Bisimulation and Coinduction. Cambridge University Press, 2012. [Sco60] D. Scott. A different kind of model for set theory. Unpublished paper, given at the 1960 Stanford Congress of Logic, Methodology and Philosophy of Science, 1960. [Sco69a] D.

G. [Coh81, MT92, Wec92]. A further step up the abstraction ladder is taken when one studies algebra with the notions and tools from category theory.

Download PDF sample

Rated 4.21 of 5 – based on 27 votes