Concurrent Games over Relational Structures: The Origin of Game Comonads

Yoàv Montacute; Glynn Winskel

doi:10.1145/3661814.3662075

Concurrent Games over Relational Structures: The Origin of Game Comonads

Yoàv Montacute, Glynn Winskel

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution book

1 Citation (Scopus)

32 Downloads (Pure)

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.

Original language	English
Title of host publication	Proceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science
Subtitle of host publication	Proceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science
Place of Publication	New York, NY
Pages	1-14
Number of pages	14
ISBN (Electronic)	9798400706608
DOIs	https://doi.org/10.1145/3661814.3662075
Publication status	Published - 8 Jul 2024
Event	LICS '24: 39th Annual ACM/IEEE Symposium on Logic in Computer Science - Tallinn, Estonia Duration: 8 Jul 2024 → 11 Jul 2024

Publication series

Name	Proceedings of the Annual ACM/IEEE Symposium on Logic in Computer Science
Publisher	ACM

Conference

Conference	LICS '24
Abbreviated title	LICS '24
Country/Territory	Estonia
City	Tallinn
Period	8/07/24 → 11/07/24

Funding

Thanks to Aurore Alcolei, Pierre Clairambault, Adam \u00D3 Conghaile, Mai Gehrke, Sacha Huriot-Tattegrain and Martin Hyland, as well as to the anonymous referees. As part of his Cambridge internship from ENS Saclay, Sacha verified the key facts about expansions [15]. Glynn Winskel was partially supported by the Huawei Research Centre, Edinburgh.

Keywords

logic
concurrent games
relational structures
game comonads

Access to Document

10.1145/3661814.3662075

Montacute-Winksel-LICS-2024-Concurrent-games-over-relational-structuresAccepted author manuscript, 686 KBLicence: Strath_1

Cite this

Montacute, Y., & Winskel, G. (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 39th Annual ACM/IEEE Symposium on Logic in Computer Science (pp. 1-14). Article 58 (Proceedings of the Annual ACM/IEEE Symposium on Logic in Computer Science).. https://doi.org/10.1145/3661814.3662075

Montacute, Yoàv ; Winskel, Glynn. / Concurrent Games over Relational Structures : The Origin of Game Comonads. Proceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science: Proceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science. New York, NY, 2024. pp. 1-14 (Proceedings of the Annual ACM/IEEE Symposium on Logic in Computer Science).

@inproceedings{e0d0f4d607564f48954e6543df62c979,

title = "Concurrent Games over Relational Structures: The Origin of Game Comonads",

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.",

keywords = "logic, concurrent games, relational structures, game comonads",

author = "Yo{\`a}v Montacute and Glynn Winskel",

year = "2024",

month = jul,

day = "8",

doi = "10.1145/3661814.3662075",

language = "English",

series = "Proceedings of the Annual ACM/IEEE Symposium on Logic in Computer Science",

publisher = "ACM",

pages = "1--14",

booktitle = "Proceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science",

note = "LICS '24 : 39th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS '24 ; Conference date: 08-07-2024 Through 11-07-2024",

}

Montacute, Y & Winskel, G 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 39th Annual ACM/IEEE Symposium on Logic in Computer Science., 58, Proceedings of the Annual ACM/IEEE Symposium on Logic in Computer Science, New York, NY, pp. 1-14, LICS '24, Tallinn, Estonia, 8/07/24. https://doi.org/10.1145/3661814.3662075

Concurrent Games over Relational Structures: The Origin of Game Comonads. / Montacute, Yoàv; Winskel, Glynn.
Proceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science: Proceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science. New York, NY, 2024. p. 1-14 58 (Proceedings of the Annual ACM/IEEE Symposium on Logic in Computer Science).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution book

TY - GEN

T1 - Concurrent Games over Relational Structures

T2 - LICS '24

AU - Montacute, Yoàv

AU - Winskel, Glynn

PY - 2024/7/8

Y1 - 2024/7/8

N2 - 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.

AB - 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.

KW - logic

KW - concurrent games

KW - relational structures

KW - game comonads

UR - https://doi.org/10.48550/arXiv.2405.11267

U2 - 10.1145/3661814.3662075

DO - 10.1145/3661814.3662075

M3 - Conference contribution book

T3 - Proceedings of the Annual ACM/IEEE Symposium on Logic in Computer Science

SP - 1

EP - 14

BT - Proceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science

CY - New York, NY

Y2 - 8 July 2024 through 11 July 2024

ER -

Montacute Y, Winskel G. 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 39th Annual ACM/IEEE Symposium on Logic in Computer Science. New York, NY. 2024. p. 1-14. 58. (Proceedings of the Annual ACM/IEEE Symposium on Logic in Computer Science). Epub 2024 Jul 8. doi: 10.1145/3661814.3662075

Concurrent Games over Relational Structures: The Origin of Game Comonads

Abstract

Publication series

Conference

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this