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 info forms and automata with countless behaviour. in recent times, it has come to play an ever extra vital position within the idea of computing. it's studied in lots of disciplines, together with procedure idea and concurrency, modal common sense and automata conception. in general, coinductive proofs reveal the equivalence of 2 gadgets by way of developing an appropriate bisimulation relation among them. This choice of surveys is aimed toward either researchers and Master's scholars in desktop technology and arithmetic and bargains with numerous facets of bisimulation and coinduction, with an emphasis on method conception. Seven chapters disguise the subsequent themes: historical past, algebra and coalgebra, algorithmics, common sense, higher-order languages, improvements of the bisimulation evidence procedure, and chances. 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 evidence technique (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

Swarm Intelligence: Introduction and Applications

The book’s contributing authors are one of the best researchers in swarm intelligence. The publication is meant to supply an summary of the topic to newcomers, and to provide researchers an replace on fascinating contemporary advancements. Introductory chapters care for the organic foundations, optimization, swarm robotics, and purposes in new-generation telecommunication networks, whereas the second one half comprises chapters on extra particular issues of swarm intelligence learn.

The Universe as Automaton: From Simplicity and Symmetry to Complexity

This Brief is an essay on the interface of philosophy and complexity learn, attempting to encourage the reader with new rules and new conceptual advancements of mobile automata. Going past the numerical experiments of Steven Wolfram, it really is argued that mobile automata needs to be thought of complicated dynamical structures of their personal correct, requiring applicable analytical versions on the way to locate targeted solutions and predictions within the universe of mobile automata.

Computability Theory. An Introduction

This ebook introduces the most important thoughts, structures, and theorems of the ordinary conception of computability of recursive services. It emphasizes the concept that of "effective approach" early with a purpose to supply a transparent, intuitive figuring out of potent computability (as on the topic of services and units) earlier than continuing to the rigorous section of the booklet.

Advances in Combinatorial Optimization: Linear Programming Formulations of the Traveling Salesman and Other Hard Combinatorial Optimization Problems

Combinational optimization (CO) is a subject in utilized arithmetic, selection technological know-how and laptop technological know-how that involves discovering the easiest answer from a non-exhaustive seek. CO is expounded to disciplines reminiscent of computational complexity conception and set of rules conception, and has vital purposes in fields corresponding to operations research/management technological know-how, man made intelligence, computer studying, and software program engineering.

Additional info for Advanced Topics in Bisimulation and Coinduction

Example text

Also, the fixed-point properties of the Y combinator of the λ-calculus had been known for a long time (used for instance by Curry, Feys, Landin, and Strachey), but the precise mathematical meaning of Y as fixed point remains unclear until Scott works out his theory of reflexive domains, at the end of 1969 [Sco69b, Sco69a]; see [Par70]. (Another relevant paper is [Sco69c], in which fixed points appear but which precedes the discovery of reflexive domains. We may also recall James H. ) During the 1970s, further fixed-point techniques and rules are put forward.

IEEE, 1977. Final version in Computing, 21(4):273– 294, 1979. Based on Clarke’s PhD thesis, Completeness and Incompleteness Theorems for Hoare-like Axiom Systems, Cornell University, 1976. V. Devid´e. On monotonous mappings of complete lattices. Fundamenta Mathematicae, LIII:147–154, 1963. P. de Roever. On backtracking and greatest fixpoints. In Arto Salomaa and Magnus Steinby, editors, Fourth Colloquium on Automata, Languages and Programming (ICALP), volume 52 of Lecture Notes in Computer Science, pages 412–429.

Greatest fixed points, and related coinductive techniques, begin to appear as well in the 1970s. It is hard to tell what is the first appearance. One reason for this is that the rules for greatest fixed points are not surprising, being the dual of rules for least fixed points that had already been studied. I would think however that the first to make explicit and non-trivial use of greatest fixed points is David Park, who, throughout the 1970s, works intensively on fairness issues for programs that may contain constructs for parallelism and that may not terminate.

Download PDF sample

Rated 4.98 of 5 – based on 16 votes