IFIP Logo
Sign in for Members and Observers

IFIP WG1.3 Foundations of System Specification


Talk "Hennessy-Milner Theorems via Galois Connections"

by Barbara König

Tue, 25 April 2023 at 02:00 pm in Paris, France

Joint work with: Harsh Beohar, Sebastian Gurke, Karla Messing

Abstract: We introduce a general and compositional, yet simple, framework that allows to derive soundness and expressiveness results for modal logics characterizing behavioural equivalences or metrics (also known as Hennessy-Milner theorems). It is based on Galois connections between sets of (real-valued) predicates on the one hand and equivalence relations/metrics on the other hand and covers a part of the linear-time-branching-time spectrum, both for the qualitative case (behavioural equivalences) and the quantitative case (behavioural metrics). We derive behaviour functions from a given logic and give a condition, called compatibility, that characterizes under which conditions a logically induced equivalence/metric is induced by a fixpoint equation. In particular, this framework allows to derive a new fixpoint characterization of directed trace metrics.

Slides