Conformance Games for Graded Semantics

Forster J, 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: 555-567

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

Event location: Singapore, SGP SG

ISBN: 9798331554644

DOI: 10.1109/LICS65433.2025.00048

Abstract

Game-theoretic characterizations of process equivalences traditionally form a central topic in concurrency; for example, most equivalences on the classical linear-time / branching-time spectrum come with such characterizations. Recent work on so-called graded semantics has led to a generic behavioural equivalence game that covers the mentioned games on the linear-time / branching-time spectrum and moreover applies in coalgebraic generality, and thus instantiates also to equivalence games on systems with non-relational branching type (probabilistic, weighted, game-based etc.). In the present work, we generalize this approach to cover other types of process comparison beyond equivalence, such as behavioural preorders or pseudometrics. At the most general level, we abstract such notions of behavioural conformance in terms of topological categories, and later specialize to conformances presented as relational structures to obtain a concrete syntax. We obtain a sound and complete generic game for behavioural conformances in this sense. We present a number of instantiations, obtaining game characterizations of, e.g., trace inclusion, probabilistic trace distance, bisimulation topologies, and simulation distances on metric labelled transition systems.

Authors with CRIS profile

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

How to cite

APA:

Forster, J., Schröder, L., & Wild, P. (2025). Conformance Games for Graded Semantics. In Proceedings - Symposium on Logic in Computer Science (pp. 555-567). Singapore, SGP, SG: Institute of Electrical and Electronics Engineers Inc..

MLA:

Forster, Jonas, Lutz Schröder, and Paul Wild. "Conformance Games for Graded Semantics." 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. 555-567.

BibTeX: Download