License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CSL.2021.16
URN: urn:nbn:de:0030-drops-134501
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/13450/
Go to the corresponding LIPIcs Volume Portal

Conghaile, Adam Ó ; Dawar, Anuj

Game Comonads & Generalised Quantifiers

pdf-format:
LIPIcs-CSL-2021-16.pdf (0.6 MB)

Abstract

Game comonads, introduced by Abramsky, Dawar and Wang and developed by Abramsky and Shah, give an interesting categorical semantics to some Spoiler-Duplicator games that are common in finite model theory. In particular they expose connections between one-sided and two-sided games, and parameters such as treewidth and treedepth and corresponding notions of decomposition. In the present paper, we expand the realm of game comonads to logics with generalised quantifiers. In particular, we introduce a comonad graded by two parameter n ≤ k such that isomorphisms in the resulting Kleisli category are exactly Duplicator winning strategies in Hella’s n-bijection game with k pebbles. We define a one-sided version of this game which allows us to provide a categorical semantics for a number of logics with generalised quantifiers. We also give a novel notion of tree decomposition that emerges from the construction.

BibTeX - Entry

@InProceedings{conghaile_et_al:LIPIcs:2021:13450,
  author =	{Adam Ó Conghaile and Anuj Dawar},
  title =	{{Game Comonads & Generalised Quantifiers}},
  booktitle =	{29th EACSL Annual Conference on Computer Science Logic (CSL 2021)},
  pages =	{16:1--16:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-175-7},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{183},
  editor =	{Christel Baier and Jean Goubault-Larrecq},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/13450},
  URN =		{urn:nbn:de:0030-drops-134501},
  doi =		{10.4230/LIPIcs.CSL.2021.16},
  annote =	{Keywords: Logic, Finite Model Theory, Game Comonads, Generalised Quantifiers}
}

Keywords: Logic, Finite Model Theory, Game Comonads, Generalised Quantifiers
Collection: 29th EACSL Annual Conference on Computer Science Logic (CSL 2021)
Issue Date: 2021
Date of publication: 13.01.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI