Towards a unified view of bisimulation: a comparative study

摘要

The realm of approaches to operational descriptions and equivalences for concurrent systems in the literature lead to a series of different attempts to give a uniform characterization of what should be considered a bisimulation, mostly in an algebraic and/or categorical framework. Meanwhile the realm of such approaches calls itself for comparison and/or unification. We investigate how different abstract characterizations of bisimulations are related. In particular, we consider the coalgebraic approach of Aczel and Mendler, the observation structures (Kripke structures) of Degano, De Nicola and Montanari, the algebraic approach of Malacaria, the domain theoretic view of Abramsky and the categorical setting of Joyal, Nielsen and Winskel. The framework of Aczel and Mendler turns out to be the most general one in the sense that the other approaches can be translated into it. These translations, where the relation between the categorical setting of Joyal, Nielsen and Winskel with the coalgebraic approach is the most complicated one, enhance the understanding of the different approaches and contribute to a unified view of bisimulation. (C) 2000 Elsevier Science B.V. All rights reserved. [References: 34]