Monday, November 12, 2007

The Origins of Bisimulation and Coinduction

I recently finished reading the paper On the Origins of Bisimulation, Coinduction, and Fixed Points by Davide Sangiorgi.

I had the pleasure of hearing Davide give a talk on the topic of this survey paper during a workshop I co-organized in August 2005 in Bertinoro, and I had been waiting for the paper to appear in print ever since. The wait has now been vindicated by this truly excellent piece of scholarship. I suggest that any reader of this blog grabs a copy of this paper and reads it. I myself learned something new from it and enjoyed reading it immensely.

In this well-organized paper, Davide takes us on a historical journey tracing back the origins of the ideas of bisimulation and coinduction through the three fields where they emerged independently: Computer Science, Modal Logic and Set Theory. He highlights the role played by some key figures in the development of bisimulation and co-induction, but he does not forget to mention the interesting contributions of less-known players. Each section of the paper ends with a discussion of the ideas it presents and speculates on the reasons why some authors went very close to defining bisimulation, but did not take the extra step needed to discover/invent bisimilarity.

The level of scholarship in the paper is outstanding. We need to thank Davide for making the effort to find appropriate sources, to read them so carefully and to present his findings in such a well-organized survey paper.

I trust that the writing of this paper took a lot of work and I hope that our community will recognize the importance of writing articles like this one. Shouldn't journals accept historical papers of this quality? I believe they should!

Thanks again to Davide for making the effort to write this piece. I firmly believe that we should have more articles like this one and hope that this paper will enjoy a wide readership throughout the TCS community as a whole.

No comments: