Abramsky, S; Reggio, L; (2023) Arboreal Categories: an Axiomatic Theory of Resources. Logical Methods in Computer Science , 19 (3) 10.46298/lmcs-19(3:14)2023.

Preview

Text Abramsky, Reggio - Arboreal Categories, An Axiomatic Theory of Resources.pdf - Published Version Download (584kB) | Preview

Abstract

Game comonads provide a categorical syntax-free approach to finite model theory, and their Eilenberg-Moore coalgebras typically encode important combinatorial parameters of structures. In this paper, we develop a framework whereby the essential properties of these categories of coalgebras are captured in a purely axiomatic fashion. To this end, we introduce arboreal categories, which have an intrinsic process structure, allowing dynamic notions such as bisimulation and back-and-forth games, and resource notions such as number of rounds of a game, to be defined. These are related to extensional or “static” structures via arboreal covers, which are resource-indexed comonadic adjunctions. These ideas are developed in a general, axiomatic setting, and applied to relational structures, where the comonadic constructions for pebbling, Ehrenfeucht-Fraïssé and modal bisimulation games recently introduced by Abramsky, Dawar et al. are recovered, showing that many of the fundamental notions of finite model theory and descriptive complexity arise from instances of arboreal covers.

Download activity - last month

Export as CSVJSONXML

Download activity - last 12 months

Export as CSVXMLJSON

Downloads by country - last 12 months

Export as CSVJSONXML

Archive Staff Only

View Item