Relators and Notions of Simulation Revisited

Goncharov S, Hofmann D, Nora P, Schröder L, Wild P (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: 776-789

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

Event location: Singapore, SGP SG

ISBN: 9798331554644

DOI: 10.1109/LICS65433.2025.00064

Abstract

Simulations and bisimulations are ubiquitous in the study of concurrent systems and modal logics of various types. Besides classical relational transition systems, relevant system types include, for instance, probabilistic, weighted, neighbourhood-based, and game-based systems. Universal coalgebra abstracts system types in this sense as set functors. Notions of (bi)simulation then arise by extending the functor to act on relations in a suitable manner, turning it into what may be termed a relator. We contribute to the study of relators in the broadest possible sense, in particular in relation to their induced notions of (bi)similarity. Specifically, (i) we show that every functor that preserves a very restricted type of pullbacks (termed 1/4-iso pullbacks) admits a sound and complete notion of bisimulation induced by the coBarr relator; (ii) we establish equivalences between properties of relators and closure properties of the induced notion of (bi)simulation, showing in particular that the full set of expected closure properties requires the relator to be a lax extension, and that soundness of (bi)simulations requires preservation of diagonals; and (iii) we show that functors preserving inverse images admit a greatest lax extension. In a concluding case study, we apply (iii) to obtain a novel highly permissive notion of twisted bisimulation on labelled transition systems.

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

University of Birmingham GB United Kingdom (GB) Center for Research & Development in Mathematics and Applications / Centro de Investigação e Desenvolvimento em Matemática e Aplicações (CIDMA) PT Portugal (PT) Radboud University Nijmegen NL Netherlands (NL)

How to cite

APA:

Goncharov, S., Hofmann, D., Nora, P., Schröder, L., & Wild, P. (2025). Relators and Notions of Simulation Revisited. In Proceedings - Symposium on Logic in Computer Science (pp. 776-789). Singapore, SGP, SG: Institute of Electrical and Electronics Engineers Inc..

MLA:

Goncharov, Sergey, et al. "Relators and Notions of Simulation Revisited." Proceedings of the 40th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2025, Singapore, SGP Institute of Electrical and Electronics Engineers Inc., 2025. 776-789.

BibTeX: Download