Arboreal categories and equi-resource homomorphism preservation theorems

DOI10.1016/j.apal.2024.103423arXiv2211.15808MaRDI QIDQ6131200

Samson Abramsky, Luca Reggio

Publication date: 4 April 2024

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

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

zbMATH Keywords

modal logicfirst-order logicguarded logicsgame comonadshomomorphism preservation theoremslogical resources

Mathematics Subject Classification ID

Logic in computer science (03B70) Semantics in the theory of computing (68Q55) Classical first-order logic (03B10) Model theory of finite structures (03C13) Theories (e.g., algebraic theories), structure, and semantics (18C10) Descriptive complexity and finite models (68Q19)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The core of a graph
• Elements of finite model theory.
• Abstract elementary classes and accessible categories
• Properties preserved under homomorphism
• Upper and lower bounds for first order expressibility
• Modal languages and bounded fragments of predicate logic
• A completeness theorem for open maps
• A note on graded modal logic
• A pebbling comonad for finite rank and variable logic, and an application to the equirank-variable homomorphism preservation theorem
• Whither semantics?
• Tree-depth, subgraph coloring and homomorphism bounds
• Categories of continuous functors. I
• An application of games to the completeness problem for formalized theories
• Homomorphism preservation theorems
• On Moschovakis closure ordinals
• Structure and Power: an Emerging Landscape
• Relating Structure and Power: Comonadic Semantics for Computational Resources
• Relating structure and power: Comonadic semantics for computational resources
• Foundations of Software Science and Computation Structures
• Completely Distributive Complete Lattices
• On the extending of models (I)
• Arboreal Categories: An Axiomatic Theory of Resources

This page was built for publication: Arboreal categories and equi-resource homomorphism preservation theorems