Arboreal Categories: An Axiomatic Theory of Resources

DOI10.46298/LMCS-19(3:14)2023arXiv2102.08109MaRDI QIDQ6135784FDOQ6135784

Authors: Samson Abramsky, Luca Reggio 

Publication date: 26 August 2023

Published in: Logical Methods in Computer Science (Search for Journal in Brave)

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"iss'e and modal bisimulation games recently introduced by Abramsky et al. are recovered, showing that many of the fundamental notions of finite model theory and descriptive complexity arise from instances of arboreal covers.

Full work available at URL: https://arxiv.org/abs/2102.08109

zbMATH Keywords

embeddingfinite model theorycoalgebragamebisimulationcomonadresourcesfactorisation systemrelational structuresopen maps

Mathematics Subject Classification ID

Logic in computer science (03B70) Computer science (68-XX)

Cites Work

• Title not available (Why is that?)
• On full abstraction for PCF: I, II and III
• Full abstraction for PCF
• Bisimulation from open maps
• Tree-depth, subgraph coloring and homomorphism bounds
• Categories of continuous functors. I
• Title not available (Why is that?)
• Title not available (Why is that?)
• Elements of finite model theory.
• Completely Distributive Complete Lattices
• Treewidth. Computations and approximations
• Homomorphism preservation theorems
• On the expressive power of Datalog: tools and a case study.
• Title not available (Why is that?)
• Relating Structure and Power: Comonadic Semantics for Computational Resources
• Relating structure and power: Comonadic semantics for computational resources
• Structure and Power: an Emerging Landscape

Cited In (2)

• The pebble-relation comonad in finite model theory
• Arboreal categories and equi-resource homomorphism preservation theorems

This page was built for publication: Arboreal Categories: An Axiomatic Theory of Resources

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6135784)