Home

On the origins of Bisimulation, Coinduction, and Fixed Points

Davide Sangiorgi, On the origins of Bisimulation, Coinduction, and Fixed Points.

The origins of bisimulation and bisimilarity are examined, in the three fields where they have been independently discovered: Computer Science, Philosophical Logic (precisely, Modal Logic), Set Theory.

Bisimulation and bisimilarity are coinductive notions, and as such are intimately related to fixed points, in particular greatest fixed points. Therefore also the appearance of coinduction and fixed points are discussed, though in this case only within Computer Science. The paper ends with some historical remarks on the main fixed-point theorems (such as Knaster-Tarski) that underpin the fixed-point theory presented.

There is a wealth of interesting information in this paper. Alas, it is not very easy to read, and the exposition can be improved. So this is not for beginners or outsiders, but if you are familiar with the topic the historical discussion will be of interest.

By Ehud Lamm at 2007-11-03 06:24 | History | Theory | other blogs | 9485 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

[Off-Topic] Metablogorrhetical Exposition

Could you explicate how you came across this paper? Was it cited somewhere? Was it in a journal you read? Were you given it to evaluate?

Often, links-to-papers on LTU appear out of the sky. The papers are universally interesting and sometimes brilliant -- and a coinduction-fixedpoint isomorphism, given the unfold-trampoline-continuation-recursion similarities, seems interesting.

But knowing how each paper is discovered would help democratize the posting process (if such a thing is indeed desired).

By aed at Sun, 2007-11-04 05:19 | login or register to post comments

There are quite a few

There are quite a few mailing lists, on which people announce their papers. We often mention where links come from, but when the lists are well known around here, I am sometimes lazy about doing so. I think that in this case it was the TYPES forum (you can google it).

By Ehud Lamm at Sun, 2007-11-04 05:29 | login or register to post comments

Yes

This paper was announced on the TYPES list.

By Matt Hellige at Mon, 2007-11-05 20:48 | login or register to post comments

Who is his audience?

the exposition can be improved

I have to agree with you, Ehud. I kept wondering who this report was aimed at, since it was too technical to serve as an intro to the field, but was technical enough that you pretty much needed to know what he was talking about in each area to make any sense of it.

It's a nice summary of the field across all its facets, and may be a fruitful literature review for someone who was expert in, say, π calculus bisimulation, and wanted to know more about how it fits with, say AFA set theory or model logic. But you would have to think this would be a relatively small audience. ;-)

Coincidentally, I'm currently reading Sangiorgi's book (with Walker) on the π calculus, and I'm finding it to have some of the same failings, in the sense that if I hadn't already read Milner's book, I think I would be horribly at sea.

It seems thorough and comprehensive though.

By Marc Hamann at Sun, 2007-11-04 19:51 | login or register to post comments