Simulation and final coalgebras

Add to your list(s) Download to your calendar using vCal

• Paul Levy
• Tuesday 13 October 2009, 13:00-14:00
• CS 124.

If you have a question about this talk, please contact Dan Ghica.

There are a plethora of equivalences and preorders that have been studied on processes (or imperative nondeterministic programs). Some of these, such as bisimilarity, similarity and 2-nested similarity are “branching time”, which means that they depend on what point in execution a nondeterministic choice is made.

One well-known way of characterizing bisimilarity is to build a coalgebra (i.e. transition system) that is final (i.e. any transition system can be mapped into it in a unique way that maintains the behaviours). Two processes are bisimilar when they have the same image in the final coalgebra.

It is not so well-known that similarity can be characterized in an analogous way. In this case the coalgebras are posets, and P is similar to Q when the image of P is below the image of Q.

This can be developed within an algebraic framework that has other instances such as 2-nested similarity, and – for transition systems with divergence – lower similarity and upper similarity. (Work in progress)

This talk is part of the Lab Lunch series.

This talk is included in these lists:

• CS 124
• Lab Lunch

Note that ex-directory lists are not shown.