| | |
| | |
Stat |
Members: 3643 Articles: 2'488'730 Articles rated: 2609
29 March 2024 |
|
| | | |
|
Article overview
| |
|
Relating Structure and Power: Extended Version | Samson Abramsky
; Nihil Shah
; | Date: |
13 Oct 2020 | 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-Fraisse 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-Fraisse 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. | Source: | arXiv, 2010.06496 | Services: | Forum | Review | PDF | Favorites |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser claudebot
|
| |
|
|
|
| News, job offers and information for researchers and scientists:
| |