Hostname: page-component-7b7567c8c-tnkh4 Total loading time: 0 Render date: 2026-11-16T12:31:44.194Z Has data issue: false hasContentIssue false

A survey of modal logics characterising behavioural equivalences for non-deterministic and stochastic systems

Published online by Cambridge University Press:  01 February 2008

MARCO BERNARDO
Affiliation:
Università di Urbino ‘Carlo Bo’, Istituto di Scienze e Tecnologie dell'Informazione, Italy
STEFANIA BOTTA
Affiliation:
Università di Urbino ‘Carlo Bo’, Istituto di Scienze e Tecnologie dell'Informazione, Italy
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

Behavioural equivalences are a means of establishing whether computing systems possess the same properties. The specific set of properties that are preserved by a specific behavioural equivalence clearly depends on how the system behaviour is observed and can usually be characterised by means of a modal logic. In this paper we consider three different approaches to the definition of behavioural equivalences – bisimulation, testing and trace – applied to three different classes of systems – non-deterministic, probabilistic and Markovian – and we survey the nine resulting modal logic characterisations, each of which stems from the Hennessy–Milner logic. We then compare the nine characterisations with respect to the logical operators, in order to emphasise the differences between the three approaches in the definition of behavioural equivalences and the regularities within each of them. In the probabilistic and Markovian cases we also address the issue of whether the probabilistic and temporal aspects should be treated in a local or global way and consequently whether the modal logic interpretation should be qualitative or quantitative.

Information

Type
Paper
Copyright
Copyright © Cambridge University Press2008