Graded Monads and Behavioural Equivalence Games

Ford M, Milius S, Schröder L, Beohar H, König B (2022)

Publication Type: Conference contribution

Publication year: 2022

Journal

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

Publisher: Institute of Electrical and Electronics Engineers Inc.

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

Event location: Haifa, ISR

ISBN: 9781450393515

DOI: 10.1145/3531130.3533374

Abstract

The framework of graded semantics uses graded monads to capture behavioural equivalences of varying granularity, for example as found in the linear-time / branching-time spectrum, over general system types. We describe a generic Spoiler-Duplicator game for graded semantics that is extracted from the given graded monad, and may be seen as playing out an equational proof; instances include standard pebble games for simulation and bisimulation as well as games for trace-like equivalences and coalgebraic behavioural equivalence. Considerations on an infnite variant of such games lead to a novel notion of infnite-depth graded semantics. Under reasonable restrictions, the infnite-depth graded semantics associated to a given graded equivalence can be characterized in terms of a determinization construction for coalgebras under the equivalence at hand.

Authors with CRIS profile

Matthew Ford Lehrstuhl für Informatik 8 (Theoretische Informatik) Stefan Milius Lehrstuhl für Informatik 8 (Theoretische Informatik) Lutz Schröder Lehrstuhl für Informatik 8 (Theoretische Informatik)

Related research project(s)

Cyberkriminalität und forensische Informatik (Cybercrime) Oct. 1, 2019 - March 31, 2024

Involved external institutions

Universität Duisburg-Essen (UDE) DE Germany (DE) University of Sheffield GB United Kingdom (GB)

How to cite

APA:

Ford, M., Milius, S., Schröder, L., Beohar, H., & König, B. (2022). Graded Monads and Behavioural Equivalence Games. In Proceedings - Symposium on Logic in Computer Science. Haifa, ISR: Institute of Electrical and Electronics Engineers Inc..

MLA:

Ford, Matthew, et al. "Graded Monads and Behavioural Equivalence Games." Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2022, Haifa, ISR Institute of Electrical and Electronics Engineers Inc., 2022.

BibTeX: Download