Conference item icon

Conference item

The pebbling comonad in finite model theory

Abstract:

Pebble games are a powerful tool in the study of finite model theory, constraint satisfaction and database theory. Monads and comonads are basic notions of category theory which are widely used in semantics of computation and in modern functional programming. We show that existential kpebble games have a natural comonadic formulation. Winning strategies for Duplicator in the k-pebble game for structures A and B are equivalent to morphisms from A to B in the coKleisli category for this comonad...

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed

Actions


Access Document


Files:
Publisher copy:
10.1109/LICS.2017.8005129

Authors


More by this author
Institution:
University of Oxford
Oxford college:
Wolfson College
Role:
Author
Publisher:
IEEE Publisher's website
Host title:
2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)
Publication date:
2017-08-18
Acceptance date:
2017-03-27
DOI:
Source identifiers:
710341
ISBN:
9781509030187
Pubs id:
pubs:710341
UUID:
uuid:40a3dfc2-2b15-4a0d-ae2b-fcbbc06db125
Local pid:
pubs:710341
Deposit date:
2017-08-03

Terms of use


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP