# Arboreal Categories: An Axiomatic Theory of Resources

@article{Abramsky2021ArborealCA, title={Arboreal Categories: An Axiomatic Theory of Resources}, author={Samson Abramsky and Luca Reggio}, journal={ArXiv}, year={2021}, volume={abs/2102.08109} }

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 very general, axiomatic setting, and applied to relational structures, where the comonadic constructions for pebbling… Expand

#### 2 Citations

Arboreal Categories and Resources

- Computer Science
- ICALP
- 2021

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… Expand

The Pebble-Relation Comonad in Finite Model Theory

- Computer Science, Mathematics
- ArXiv
- 2021

The pebbling comonad, introduced by Abramsky, Dawar and Wang, provides a categorical interpretation for the k-pebble games from finite model theory. The coKleisli category of the pebbling comonad… Expand

#### References

SHOWING 1-10 OF 28 REFERENCES

Relating Structure and Power: Comonadic Semantics for Computational Resources

- Computer Science
- CSL
- 2018

The 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. Expand

Comonadic semantics for guarded fragments

- Computer Science, Mathematics
- 2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)
- 2021

A systematic account of how a range of model comparison games which play a central role in finite model theory can be captured in terms of resource-indexed comonads on the category of relational structures, including Ehrenfeucht-Fraïssé, pebbling, and bisimulation games, is extended to quantifier-guarded fragments of first-order logic. Expand

Bisimulation and open maps

- Mathematics, Computer Science
- [1993] Proceedings Eighth Annual IEEE Symposium on Logic in Computer Science
- 1993

An abstract definition of bisimulation is presented and a promising new model, presheaf on categories of pomsets, into which the usual category of labeled event structures embeds fully and faithfully is presented. Expand

Bisimulation from Open Maps

- Computer Science, Mathematics
- Inf. Comput.
- 1996

A logic, generalising Hennessy?Milner logic, which is characteristic for the generalised notion of bisimulation is presented, which makes possible a uniform definition of bisIMulation across a range of different models for parallel computation presented as categories. Expand

Full Abstraction for PCF

- Computer Science, Mathematics
- Inf. Comput.
- 1994

An intensional model for the programming language PCF is described, in which the types of PCF are interpreted by games, and the terms by certain "history-free" strategies. This model is shown to… Expand

On Full Abstraction for PCF: I, II, and III

- Computer Science
- Inf. Comput.
- 2000

An order-extensional, order (or inequationally) fully abstract model for Scott's language pcf, based on a kind of game in which each play consists of a dialogue of questions and answers between two players who observe the following principles of civil conversation. Expand

Homomorphism preservation theorems

- Mathematics, Computer Science
- JACM
- 2008

It is proved that the h.p.t. remains valid when restricted to finite structures (unlike many other classical preservation theorems, including the Łoś--Tarski theorem and Lyndon's positivity theorem). Expand

∞-Categories for the Working Mathematician

- 2018

homotopy theory C.1. Lifting properties, weak factorization systems, and Leibniz closure C.1.1. Lemma. Any class of maps characterized by a right lifting property is closed under composition,… Expand

FACTORIZATION SYSTEMS

- 2008

These notes were written to accompany a talk given in the Algebraic Topology and Category Theory Proseminar in Fall 2008 at the University of Chicago. We first introduce orthogonal factorization… Expand

Tree-depth, subgraph coloring and homomorphism bounds

- Computer Science, Mathematics
- Eur. J. Comb.
- 2006

The notions tree-depth and upper chromatic number of a graph are defined and it is shown that the upper chromatics number coincides with the maximal function which can be locally demanded in a bounded coloring of any proper minor closed class of graphs. Expand