DROPS

Document

DOI: 10.4230/LIPIcs.CSL.2021.16

Game Comonads & Generalised Quantifiers

Authors: Adam Ó Conghaile and Anuj Dawar

Published in: LIPIcs, Volume 183, 29th EACSL Annual Conference on Computer Science Logic (CSL 2021)

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.

Cite as

Adam Ó Conghaile and Anuj Dawar. Game Comonads & Generalised Quantifiers. In 29th EACSL Annual Conference on Computer Science Logic (CSL 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 183, pp. 16:1-16:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{conghaile_et_al:LIPIcs.CSL.2021.16,
  author =	{Conghaile, Adam \'{O} and Dawar, Anuj},
  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 =	{Baier, Christel and Goubault-Larrecq, Jean},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2021.16},
  URN =		{urn:nbn:de:0030-drops-134501},
  doi =		{10.4230/LIPIcs.CSL.2021.16},
  annote =	{Keywords: Logic, Finite Model Theory, Game Comonads, Generalised Quantifiers}
}

Search Results

Documents authored by Conghaile, Adam Ó

Game Comonads & Generalised Quantifiers

Abstract

Cite as

Thanks for your feedback!

Could not send message