Relational Connectors and Heterogeneous Simulations
Nora P, Rot J, Schröder L, Wild P (2025)
Publication Type: Conference contribution
Publication year: 2025
Journal
Publisher: Springer Science and Business Media Deutschland GmbH
Book Volume: 15691 LNCS
Pages Range: 111-132
Conference Proceedings Title: Lecture Notes in Computer Science
Event location: Hamilton, ON
ISBN: 9783031908965
DOI: 10.1007/978-3-031-90897-2_6
Abstract
While behavioural equivalences among systems of the same type, such as Park/Milner bisimilarity of labelled transition systems, are an established notion, a systematic treatment of relationships between systems of different types is currently missing. We provide such a treatment in the framework of universal coalgebra, in which the type of a system (nondeterministic, probabilistic, weighted, game-based etc.) is abstracted as a set functor: We introduce relational connectors among set functors, which induce notions of heterogeneous (bi)simulation among coalgebras of the respective types. We give a number of constructions on relational connectors. In particular, we identify composition and converse operations on relational connectors; we construct corresponding identity relational connectors, showing that the latter generalize the standard Barr extension of weak-pullback-preserving functors; and we introduce a Kantorovich construction in which relational connectors are induced from relations between modalities. For Kantorovich relational connectors, one has a notion of dual-purpose modal logic interpreted over both system types, and we prove a corresponding Hennessy-Milner-type theorem stating that generalized (bi)similarity coincides with theory inclusion on finitely-branching systems. We apply these results to a number of example scenarios involving labelled transition systems with different label alphabets, probabilistic systems, and input/output conformances.
Authors with CRIS profile
Lutz Schröder
Lehrstuhl für Informatik 8 (Theoretische Informatik)
Paul Wild
Lehrstuhl für Informatik 8 (Theoretische Informatik)
Involved external institutions
Netherlands (NL)How to cite
APA:
Nora, P., Rot, J., Schröder, L., & Wild, P. (2025). Relational Connectors and Heterogeneous Simulations. In Parosh Aziz Abdulla, Delia Kesner (Eds.), Lecture Notes in Computer Science (pp. 111-132). Hamilton, ON, CA: Springer Science and Business Media Deutschland GmbH.
MLA:
Nora, Pedro, et al. "Relational Connectors and Heterogeneous Simulations." Proceedings of the 28th International Conference on Foundations of Software Science and Computation Structures, FOSSACS 2025, held as part of the International Joint Conferences on Theory and Practice of Software, ETAPS 2025, Hamilton, ON Ed. Parosh Aziz Abdulla, Delia Kesner, Springer Science and Business Media Deutschland GmbH, 2025. 111-132.
BibTeX: Download