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.2018.2
URN: urn:nbn:de:0030-drops-96698
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9669/
Go to the corresponding LIPIcs Volume Portal

Abramsky, Samson ; Shah, Nihil

Relating Structure and Power: Comonadic Semantics for Computational Resources

pdf-format:
LIPIcs-CSL-2018-2.pdf (0.5 MB)

Abstract

Combinatorial games are widely used in finite model theory, constraint satisfaction, modal logic and concurrency theory to characterize logical equivalences between structures. In particular, Ehrenfeucht-Fraïssé games, pebble games, and bisimulation games play a central role. We show how each of these types of games can be described in terms of an indexed family of comonads on the category of relational structures and homomorphisms. The index k is a resource parameter which bounds the degree of access to the underlying structure. The coKleisli categories for these comonads can be used to give syntax-free characterizations of a wide range of important logical equivalences. Moreover, the coalgebras for these indexed comonads can be used to characterize key combinatorial parameters: tree-depth for the Ehrenfeucht-Fraïssé comonad, tree-width for the pebbling comonad, and synchronization-tree depth for the modal unfolding comonad. These results pave the way for systematic connections between two major branches of the field of logic in computer science which hitherto have been almost disjoint: categorical semantics, and finite and algorithmic model theory.

BibTeX - Entry

@InProceedings{abramsky_et_al:LIPIcs:2018:9669,
  author =	{Samson Abramsky and Nihil Shah},
  title =	{{Relating Structure and Power: Comonadic Semantics for Computational Resources}},
  booktitle =	{27th EACSL Annual Conference on Computer Science Logic  (CSL 2018)},
  pages =	{2:1--2:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-088-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{119},
  editor =	{Dan Ghica and Achim Jung},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9669},
  URN =		{urn:nbn:de:0030-drops-96698},
  doi =		{10.4230/LIPIcs.CSL.2018.2},
  annote =	{Keywords: Finite model theory, combinatorial games, Ehrenfeucht-Fraiss{\'e} games, pebble games, bisimulation, comonads, coKleisli category, coalgebras of a comonad}
}

Keywords: Finite model theory, combinatorial games, Ehrenfeucht-Fraïssé games, pebble games, bisimulation, comonads, coKleisli category, coalgebras of a comonad
Collection: 27th EACSL Annual Conference on Computer Science Logic (CSL 2018)
Issue Date: 2018
Date of publication: 29.08.2018

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