Concurrent Games over Relational Structures : The Origin of Game Comonads
Montacute, Yoàv and Winskel, Glynn; (2024) Concurrent Games over Relational Structures : The Origin of Game Comonads. In: Proceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science. Proceedings of the Annual ACM/IEEE Symposium on Logic in Computer Science . ACM, EST, pp. 1-14. ISBN 9798400706608 (https://doi.org/10.1145/3661814.3662075)
Preview |
Text.
Filename: Montacute-Winksel-LICS-2024-Concurrent-games-over-relational-structures.pdf
Accepted Author Manuscript License: Strathprints license 1.0 Download (702kB)| Preview |
Abstract
Spoiler-Duplicator games are used in finite model theory to examine the expressive power of logics. Their strategies have recently been reformulated as coKleisli maps of game comonads over relational structures, providing new results in finite model theory via categorical techniques. We present a novel framework for studying Spoiler-Duplicator games by viewing them as event structures. We introduce a first systematic method for constructing comonads for all one-sided Spoiler-Duplicator games: game comonads are now realised by adjunctions to a category of games, generically constructed from a comonad in a bicategory of game schema (called signature games). Maps of the constructed categories of games are strategies and generalise coKleisli maps of game comonads; in the case of one-sided games they are shown to coincide with suitably generalised homomorphisms. Finally, we provide characterisations of strategies on two-sided Spoiler-Duplicator games; in a common special case they coincide with spans of event structures.
-
-
Item type: Book Section ID code: 89839 Dates: DateEvent8 July 2024Published8 July 2024Published Online15 April 2024AcceptedSubjects: Science > Mathematics > Electronic computers. Computer science Department: Faculty of Science > Computer and Information Sciences Depositing user: Pure Administrator Date deposited: 04 Jul 2024 15:28 Last modified: 15 Oct 2024 00:17 Related URLs: URI: https://strathprints.strath.ac.uk/id/eprint/89839