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 endless facts kinds and automata with limitless behaviour. in recent times, it has come to play an ever extra vital function within the concept of computing. it truly is studied in lots of disciplines, together with strategy concept and concurrency, modal common sense and automata conception. quite often, coinductive proofs exhibit 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 technology and arithmetic and offers with quite a few facets of bisimulation and coinduction, with an emphasis on technique thought. Seven chapters hide the subsequent themes: heritage, algebra and coalgebra, algorithmics, common sense, higher-order languages, improvements of the bisimulation facts strategy, and percentages. routines also are incorporated 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 process for higher-order languages (Andrew Pitts) — 6. improvements of the bisimulation facts technique (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

Numerical computing with IEEE floating point arithmetic: including one theorem, one rule of thumb, and one hundred and one exercises

Are you acquainted with the IEEE floating element mathematics normal? do you want to appreciate it higher? This booklet supplies a extensive evaluation of numerical computing, in a old context, with a different specialize in the IEEE normal for binary floating aspect mathematics. Key rules are constructed step-by-step, taking the reader from floating element illustration, appropriately rounded mathematics, and the IEEE philosophy on exceptions, to an knowing of the an important ideas of conditioning and balance, defined in an easy but rigorous context.

Robustness in Statistical Pattern Recognition

This booklet is worried with very important difficulties of sturdy (stable) statistical pat­ tern popularity whilst hypothetical version assumptions approximately experimental info are violated (disturbed). development acceptance thought is the sector of utilized arithmetic during which prin­ ciples and techniques are developed for category and id of items, phenomena, tactics, events, and signs, i.

Bridging Constraint Satisfaction and Boolean Satisfiability

This e-book presents an important step in the direction of bridging the parts of Boolean satisfiability and constraint delight by way of answering the query why SAT-solvers are effective on sure sessions of CSP situations that are not easy to resolve for traditional constraint solvers. the writer additionally offers theoretical purposes for selecting a specific SAT encoding for numerous vital periods of CSP circumstances.

A primer on pseudorandom generators

A clean examine the query of randomness used to be taken within the concept of computing: A distribution is pseudorandom if it can't be exotic from the uniform distribution by means of any effective process. This paradigm, initially associating effective approaches with polynomial-time algorithms, has been utilized with appreciate to a number of common periods of distinguishing tactics.

Additional info for Advanced Topics in Bisimulation and Coinduction

Example text

De Bakker. A theory of programs. Handwritten notes. , Vienna, Austria, 1969. [Seg68] K. Segerberg. 1. Theoria, 34:7–20, 1968. [Seg70] K. Segerberg. Modal logics with linear alternative relations. Theoria, 36:301– 322, 1970. [Seg71] K. Segerberg. An essay in classical modal logic. Filosofiska Studier, Uppsala, 1971. [Sko23] T. Skolem. Einige Bemerkungen zur Axiomatischen Begr¨undung der Mengenlehre. In Proceedings of the 5th Scandinavian Mathematics Congress, Helsinki, 1922, pages 217–232. Akademiska Bokhandeln, Helsinki, 1923.

Sco72b, Sco72a, Sco76]. g. g. [Maz71, Maz73, Bli77]; and the work of Ugo Montanari and colleagues in Pisa, such as [GM76] that contains notions of observations and equivalence of representations in abstract data types that today we recognise as related to fixed points via the concept of finality. Other references to the early works on fixed points can be found in Zohar Manna’s textbook [Man74]. The above works all deal with least fixed points. Greatest fixed points, and related coinductive techniques, begin to appear as well in the 1970s.

Further, the stratified approach was in line with common sense and perception (very important in Russell’s conception of science), which denies the existence of circular objects. The stratified approach remains indeed the only approach considered (in logics and set theory), up to roughly the 1960s, with the exception of Mirimanoff and Finsler that we discuss below. The stratified approach has also inspired – both in the name and in the method – type theory in computer science, notably in the works of Church, Scott, and Martin-L¨of.

Download PDF sample

Rated 4.12 of 5 – based on 26 votes