×

Bisimulation and logic. (English) Zbl 1285.68113

Sangiorgi, Davide (ed.) et al., Advanced topics in bisimulation and coinduction. Cambridge: Cambridge University Press (ISBN 978-1-107-00497-9/hbk). Cambridge Tracts in Theoretical Computer Science 52, 173-196 (2012).
From the introduction: Bisimulation is a rich concept which appears in various areas of theoretical computer science as this book testifies. Besides its origin by D. Park [Lect. Notes Comput. Sci. 104, 167–183 (1981; Zbl 0457.68049)] as a small refinement of the behavioural equivalence originally defined by M. Hennessy and R. Milner between basic concurrent processes [Lect. Notes Comput. Sci. 85, 299–309 (1980; Zbl 0441.68018); J. Assoc. Comput. Mach. 32, 137–161 (1985; Zbl 0629.68021)], it was independently, and earlier, defined and developed in the context of the model theory of modal logic (under the names of \(p\)-relations and zigzag relations) by J. van Benthem [Synth. Libr. 165, 167–247 (1984; Zbl 0875.03048)] to give an exact account of which subfamily of first-order logic is definable in modal logic. Interestingly, to make their definition of process equivalence more palatable, Hennessy and Milner introduced a modal logic to characterise it. For more details of the history of bisimulation see [ibid. 52, 1–37 (2012; Zbl 1285.68112)].
See also the review of the entire collection in [Zbl 1264.68009].
For the entire collection see [Zbl 1264.68009].

MSC:

68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
03B70 Logic in computer science
Full Text: DOI