Behavioural Conformances based on Lax Couplings

Wild P, Schröder L (2025)

Publication Type: Conference contribution

Publication year: 2025

Journal

Proceedings - Symposium on Logic in Computer Science Institute of Electrical and Electronics Engineers

Publisher: Institute of Electrical and Electronics Engineers Inc.

Pages Range: 790-803

Conference Proceedings Title: Proceedings - Symposium on Logic in Computer Science

Event location: Singapore

ISBN: 9798331554644

DOI: 10.1109/LICS65433.2025.00065

Abstract

Behavioural conformances - e.g. behavioural equivalences, distances, preorders - on a wide range of system types (non-deterministic, probabilistic, weighted etc.) can be dealt with uniformly in the paradigm of universal coalgebra. One of the most commonly used constructions for defining behavioural distances on coalgebras arises as a generalization of the well-known Wasserstein metric. In this construction, couplings of probability distributions are replaced with couplings of more general objects, depending on the functor describing the system type. In many cases, however, the set of couplings of two functor elements is empty, which causes such elements to have infinite distance even in situations where this is not desirable. We propose an approach to defining behavioural distances and preorders based on a more liberal notion of coupling where the coupled elements are matched laxly rather than on-the-nose. We thereby substantially broaden the range of behavioural conformances expressible in terms of couplings, covering, e.g., refinement of modal transition systems and behavioural distance on metric labelled Markov chains.

Authors with CRIS profile

Paul Wild Lehrstuhl für Informatik 8 (Theoretische Informatik) Lutz Schröder Lehrstuhl für Informatik 8 (Theoretische Informatik)

How to cite

APA:

Wild, P., & Schröder, L. (2025). Behavioural Conformances based on Lax Couplings. In Proceedings - Symposium on Logic in Computer Science (pp. 790-803). Singapore, SG: Institute of Electrical and Electronics Engineers Inc..

MLA:

Wild, Paul, and Lutz Schröder. "Behavioural Conformances based on Lax Couplings." Proceedings of the 40th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2025, Singapore Institute of Electrical and Electronics Engineers Inc., 2025. 790-803.

BibTeX: Download