Linear Arboreal Categories
0
š ļø
Sign in to get full access
The paper introduces the concept of linear arboreal categories, which are arboreal categories with additional axioms that exclude branching behavior. Arboreal categories were initially introduced to formalize behavioral notions like simulation, bisimulation, and resource-indexing in a categorical setting.
The authors demonstrate that every arboreal category satisfying a linearisability condition has an associated linear arboreal subcategory, which is related via an adjunction. This establishes the relationship between the pebble-relation comonad and the pebbling comonad, generalizing it further.
As a result of this new framework, the authors obtain a linear variant of the arboreal category for modal logic. This allows them to recover different linear-time equivalences between transition systems as instances of their categorical definitions.
The paper concludes with new preservation and characterization theorems relating trace inclusion and trace equivalence with different linear fragments of modal logic.
This summary was produced with help from an AI and may contain inaccuracies - check out the links to read the original source documents!
Related Papers
š ļø
0
Linear Arboreal Categories
Samson Abramsky, Yo`av Montacute, Nihil Shah
Arboreal categories, introduced by Abramsky and Reggio, axiomatise categories with tree-shaped objects. These categories provide a categorical language for formalising behavioural notions such as simulation, bisimulation, and resource-indexing. In this paper, we strengthen the axioms of an arboreal category to exclude `branching' behaviour, obtaining a notion of `linear arboreal category'. We then demonstrate that every arboreal category satisfying a linearisability condition has an associated linear arboreal subcategory related via an adjunction. This identifies the relationship between the pebble-relation comonad, of Montacute and Shah, and the pebbling comonad, of Abramsky, Dawar, and Wang, and generalises it further. As another outcome of this new framework, we obtain a linear variant of the arboreal category for modal logic. By doing so we recover different linear-time equivalences between transition systems as instances of their categorical definitions. We conclude with new preservation and characterisation theorems relating trace inclusion and trace equivalence with different linear fragments of modal logic.
Read more4/1/2024
š
0
Representing Knowledge and Querying Data using Double-Functorial Semantics
Michael Lambert, Evan Patterson
Category theory offers a mathematical foundation for knowledge representation and database systems. Popular existing approaches model a database instance as a functor into the category of sets and functions, or as a 2-functor into the 2-category of sets, relations, and implications. The functional and relational models are unified by double functors into the double category of sets, functions, relations, and implications. In an accessible, example-driven style, we show that the abstract structure of a 'double category of relations' is a flexible and expressive language in which to represent knowledge, and we show how queries on data in the spirit of Codd's relational algebra are captured by double-functorial semantics.
Read more4/1/2024
3
The Geometry of Categorical and Hierarchical Concepts in Large Language Models
Kiho Park, Yo Joong Choe, Yibo Jiang, Victor Veitch
Understanding how semantic meaning is encoded in the representation spaces of large language models is a fundamental problem in interpretability. In this paper, we study the two foundational questions in this area. First, how are categorical concepts, such as {'mammal', 'bird', 'reptile', 'fish'}, represented? Second, how are hierarchical relations between concepts encoded? For example, how is the fact that 'dog' is a kind of 'mammal' encoded? We show how to extend the linear representation hypothesis to answer these questions. We find a remarkably simple structure: simple categorical concepts are represented as simplices, hierarchically related concepts are orthogonal in a sense we make precise, and (in consequence) complex concepts are represented as polytopes constructed from direct sums of simplices, reflecting the hierarchical structure. We validate these theoretical results on the Gemma large language model, estimating representations for 957 hierarchically related concepts using data from WordNet.
Read more6/4/2024
š¤æ
2
Position: Categorical Deep Learning is an Algebraic Theory of All Architectures
Bruno Gavranovi'c, Paul Lessard, Andrew Dudzik, Tamara von Glehn, Jo~ao G. M. Ara'ujo, Petar Veliv{c}kovi'c
We present our position on the elusive quest for a general-purpose framework for specifying and studying deep learning architectures. Our opinion is that the key attempts made so far lack a coherent bridge between specifying constraints which models must satisfy and specifying their implementations. Focusing on building a such a bridge, we propose to apply category theory -- precisely, the universal algebra of monads valued in a 2-category of parametric maps -- as a single theory elegantly subsuming both of these flavours of neural network design. To defend our position, we show how this theory recovers constraints induced by geometric deep learning, as well as implementations of many architectures drawn from the diverse landscape of neural networks, such as RNNs. We also illustrate how the theory naturally encodes many standard constructs in computer science and automata theory.
Read more6/7/2024