Arboreal Categories: An Axiomatic Theory of Resources

DOI10.46298/LMCS-19(3:14)2023MaRDI QIDQ6135784zbMATH OpenFDO

Authors Samson Abramsky, Luca Reggio

Publication date 26 August 2023

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

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

bisimulationcoalgebracomonadembeddingfactorisation systemfinite model theorygameopen mapsrelational structuresresources

Mathematics Subject Classification ID

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

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.

Cites work

• Bisimulation from open maps
• Categories of continuous functors. I
• Completely Distributive Complete Lattices
• Elements of finite model theory.
• Full abstraction for PCF
• Homomorphism preservation theorems
• scientific article; zbMATH DE number 1216133 (Why is no real title available?)
• scientific article; zbMATH DE number 1748069 (Why is no real title available?)
• scientific article; zbMATH DE number 822489 (Why is no real title available?)
• On full abstraction for PCF: I, II and III
• On the expressive power of Datalog: tools and a case study.
• Relating structure and power: comonadic semantics for computational resources
• Relating structure and power: Comonadic semantics for computational resources
• Structure and Power: an Emerging Landscape
• The pebbling comonad in finite model theory
• Tree-depth, subgraph coloring and homomorphism bounds
• Treewidth. Computations and approximations

Cited in

(7)

• Arboreal categories and equi-resource homomorphism preservation theorems
• The pebble-relation comonad in finite model theory
• A categorical account of composition methods in logic
• Modal logic with relations over paths: a theoretical development through comonadic semantics
• Concurrent games over relational structures: the origin of game comonads
• Homomorphism preservation theorems for many-valued structures
• Existential and positive games: a comonadic and axiomatic view

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)