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

By Davide Sangiorgi, Jan Rutten

Coinduction is a technique for specifying and reasoning approximately limitless facts forms and automata with limitless 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 procedure thought and concurrency, modal good judgment and automata concept. often, coinductive proofs show the equivalence of 2 gadgets by means of developing an appropriate bisimulation relation among them. This number of surveys is geared toward either researchers and Master's scholars in computing device technological know-how and arithmetic and offers with quite a few points of bisimulation and coinduction, with an emphasis on procedure concept. Seven chapters disguise the subsequent subject matters: heritage, algebra and coalgebra, algorithmics, common sense, higher-order languages, improvements of the bisimulation facts strategy, and percentages. routines also are integrated to assist 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 technique for higher-order languages (Andrew Pitts) — 6. improvements of the bisimulation facts strategy (Damien Pous and Davide Sangiorgi) — 7. Probabilistic bisimulation (Prakash Panangaden)

Show description

Read Online or Download Advanced Topics in Bisimulation and Coinduction PDF

Similar machine theory books

Computational science and its applications -- ICCSA 2009 : International Conference, Seoul, Korea, June 29 - July 2, 2009, Proceedings. Part 1

The two-volume set LNCS 5592 and 5593 constitutes the refereed lawsuits of the overseas convention on Computational technological know-how and Its purposes, ICCSA 2009, held in Seoul, Korea, in June/July, 2009. the 2 volumes comprise papers providing a wealth of unique study ends up in the sphere of computational technological know-how, from foundational matters in desktop technology and arithmetic to complicated functions in nearly all sciences using computational thoughts.

Probabilistic Analysis of Algorithms: On Computing Methodologies for Computer Algorithms Performance Evaluation

Probabilistic research of Algorithms starts with a presentation of the "tools of the alternate" at the moment utilized in probabilistic analyses, and keeps with an functions part within which those instruments are utilized in the research ofr chosen algorithms. The instruments component to the e-book presents the reader with an arsenal of analytic and numeric computing tools that are then utilized to numerous teams of algorithms to research their working time or garage requisites features.

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

This booklet constitutes the completely refereed post-conference lawsuits of the ninth foreign convention on Large-Scale clinical Computations, LSSC 2013, held in Sozopol, Bulgaria, in June 2013. The seventy four revised complete papers provided including five plenary and invited papers have been rigorously reviewed and chosen from various submissions.

Duality in Vector Optimization

This publication offers basics and accomplished effects relating to duality for scalar, vector and set-valued optimization difficulties in a normal atmosphere. One bankruptcy is completely consecrated to the scalar and vector Wolfe and Mond-Weir duality schemes.

Additional resources for Advanced Topics in Bisimulation and Coinduction

Example text

The axiom AFA becomes a requirement that appropriate systems of equations have a unique solution. To understand this point consider that, as the purely reflexive set can be seen as the solution to the equation x D fxg, so all non-well-founded sets arise from systems of equations with variables on the left-hand side, and well-founded sets possibly containing such variables on the right-hand side. In Aczel [Acz88] this is expressed as the ‘solution lemma’. Barwise makes it the base assumption from which all the theory of sets is derived.

8] is from Hitchcock and Park [HP73]. Similar versions are also given by Devid´e [Dev63], Pasini [Pas74], Cadiou [Cad72], Cousot and Cousot [CC79]. A related theorem also appears in Bourbaki [Bou50]. Bibliography [Acz88] P. Aczel. Non-Well-Founded Sets. CSLI Lecture Notes, no. 14, 1988. [AIS12] L. Aceto, A. Ingolfsdottir, and J. Srba. The algorithmics of bisimilarity. Chapter 3 of this volume. N. Arden. Delayed logic and finite state machines. In Theory of Computing Machine Design, pages 1–35. University of Michigan Press, 1960.

The earliest uses of fixed points in computer science, in the form of least fixed points, can be found in recursive function theory, see for instance Rogers’s book [Rog67] and references therein, and formal language theory, as in the work of Arden [Ard60] and Ginsburg and Rice [GR62]. However, distinguishing computer science from recursive function theory, the importance of fixed points in computer science really comes up only at the end of the 1960s, with four independent papers, roughly at the same time, by Dana Scott and Jaco de Bakker [SdB69], Hans Bekiˇc [Bek69], David Park [Par69], and Antoni Muzurkiewicz [Maz71] (however [Maz71] does not make explicit reference to fixed-point theory).

Download PDF sample

Rated 4.20 of 5 – based on 16 votes