Home

Compositionality describes and quantifies how complex things can be assembled out of simpler parts. Compositionality, the journal, is an open-access, arXiv-overlay journal for research using compositional ideas, most notably of a category-theoretic origin, in any discipline. Topics may concern foundational structures, an organizing principle, or a powerful tool. Example areas include but are not limited to: mathematics, computation, logic, physics, chemistry, engineering, linguistics, and cognition.

Compositionality is free of cost for both readers and authors. You can find our editorial policies here. Our first issue was published, under ISSN 2631-4444, in December 2019.

    Recently published

    Homotopy Theoretic and Categorical Models of Neural Information Networks


    In this paper we develop a novel mathematical formalism for the modeling of neural information networks endowed with additional structure in the form of assignments of resources, either computational or metabolic or informational. The starting point for this construction is the notion of summing functors and of Segal's Gamma-spaces in homotopy theory. The main results in this paper include functorial assignments of concurrent/distributed computing architectures and associated binary codes to networks and their subsystems, a categorical form of the Hopfield network dynamics, which recovers the usual Hopfield equations when applied to a suitable category of weighted codes, a functorial assignment to networks of corresponding information structures and information cohomology, and a cohomological version of integrated information.


    Published on September 6, 2024
    A Framework for Universality in Physics, Computer Science, and Beyond


    Turing machines and spin models share a notion of universality according to which some simulate all others. Is there a theory of universality that captures this notion? We set up a categorical framework for universality which includes as instances universal Turing machines, universal spin models, NP completeness, top of a preorder, denseness of a subset, and more. By identifying necessary conditions for universality, we show that universal spin models cannot be finite. We also characterize when universality can be distinguished from a trivial one and use it to show that universal Turing machines are non-trivial in this sense. Our framework allows not only to compare universalities within each instance, but also instances themselves. We leverage a Fixed Point Theorem inspired by a result of Lawvere to establish that universality and negation give rise to unreachability (such as uncomputability). As such, this work sets the basis for a unified approach to universality and invites the study of further examples within the framework.


    Published on August 29, 2024
    A compositional account of motifs, mechanisms, and dynamics in biochemical regulatory networks


    Regulatory networks depict promoting or inhibiting interactions between molecules in a biochemical system. We introduce a category-theoretic formalism for regulatory networks, using signed graphs to model the networks and signed functors to describe occurrences of one network in another, especially occurrences of network motifs. With this foundation, we establish functorial mappings between regulatory networks and other mathematical models in biochemistry. We construct a functor from reaction networks, modeled as Petri nets with signed links, to regulatory networks, enabling us to precisely define when a reaction network could be a physical mechanism underlying a regulatory network. Turning to quantitative models, we associate a regulatory network with a Lotka-Volterra system of differential equations, defining a functor from the category of signed graphs to a category of parameterized dynamical systems. We extend this result from closed to open systems, demonstrating that Lotka-Volterra dynamics respects not only inclusions and collapsings of regulatory networks, but also the process of building up complex regulatory networks by gluing together simpler pieces. Formally, we use the theory of structured cospans to produce a lax double functor from the double category of open signed graphs to that of open parameterized dynamical systems. Throughout the paper, we ground the categorical formalism in examples inspired by systems biology.


    Published on May 13, 2024
    Profunctor Optics, a Categorical Update


    Optics are bidirectional data accessors that capture data transformation patterns such as accessing subfields or iterating over containers. Profunctor optics are a particular choice of representation supporting modularity, meaning that we can construct accessors for complex structures by combining simpler ones. Profunctor optics have previously been studied only in an unenriched and non-mixed setting, in which both directions of access are modelled in the same category. However, functional programming languages are arguably better described by enriched categories; and we have found that some structures in the literature are actually mixed optics, with access directions modelled in different categories. Our work generalizes a classic result by Pastro and Street on Tambara theory and uses it to describe mixed V-enriched profunctor optics and to endow them with V-category structure. We provide some original families of optics and derivations, including an elementary one for traversals. Finally, we discuss a Haskell implementation.


    Published on February 23, 2024
    Traced Monads and Hopf Monads


    A traced monad is a monad on a traced symmetric monoidal category that lifts the traced symmetric monoidal structure to its Eilenberg-Moore category. A long-standing question has been to provide a characterization of traced monads without explicitly mentioning the Eilenberg-Moore category. On the other hand, a symmetric Hopf monad is a symmetric bimonad whose fusion operators are invertible. For compact closed categories, symmetric Hopf monads are precisely the kind of monads that lift the compact closed structure to their Eilenberg-Moore categories. Since compact closed categories and traced symmetric monoidal categories are closely related, it is a natural question to ask what is the relationship between Hopf monads and traced monads. In this paper, we introduce trace-coherent Hopf monads on traced monoidal categories, which can be characterized without mentioning the Eilenberg-Moore category. The main theorem of this paper is that a symmetric Hopf monad is a traced monad if and only if it is a trace-coherent Hopf monad. We provide many examples of trace-coherent Hopf monads, such as those induced by cocommutative Hopf algebras or any symmetric Hopf monad on a compact closed category. We also explain how for traced Cartesian monoidal categories, trace-coherent Hopf monads can be expressed using the Conway operator, while for traced coCartesian monoidal categories, any trace-coherent Hopf monad is an idempotent monad. We also provide separating examples of traced monads that […]


    Published on October 30, 2023
    Bayesian open games


    This paper generalises the treatment of compositional game theory as introduced by Ghani et al. in 2018, where games are modelled as morphisms of a symmetric monoidal category. From an economic modelling perspective, the notion of a game in the work by Ghani et al. is not expressive enough for many applications. This includes stochastic environments, stochastic choices by players, as well as incomplete information regarding the game being played. The current paper addresses these three issues all at once.


    Published on October 4, 2023
    Substructural fixed-point theorems and the diagonal argument: theme and variations


    This article re-examines Lawvere's abstract, category-theoretic proof of the fixed-point theorem whose contrapositive is a `universal' diagonal argument. The main result is that the necessary axioms for both the fixed-point theorem and the diagonal argument can be stripped back further, to a semantic analogue of a weak substructural logic lacking weakening or exchange.


    Published on August 10, 2023
    Degrees in random $m$-ary hooking networks


    The theme in this paper is a composition of random graphs and P\'olya urns. The random graphs are generated through a small structure called the seed. Via P\'olya urns, we study the asymptotic degree structure in a random $m$-ary hooking network and identify strong laws. We further upgrade the result to second-order asymptotics in the form of multivariate Gaussian limit laws. We give a few concrete examples and explore some properties with a full representation of the Gaussian limit in each case. The asymptotic covariance matrix associated with the P\'olya urn is obtained by a new method that originated in this paper and is reported in [25].


    Published on August 9, 2023
    Monotones in General Resource Theories


    A central problem in the study of resource theories is to find functions that are nonincreasing under resource conversions - termed monotones - in order to quantify resourcefulness. Various constructions of monotones appear in many different concrete resource theories. How general are these constructions? What are the necessary conditions on a resource theory for a given construction to be applicable? To answer these questions, we introduce a broad scheme for constructing monotones. It involves finding an order-preserving map from the preorder of resources of interest to a distinct preorder for which nontrivial monotones are previously known or can be more easily constructed; these monotones are then pulled back through the map. In one of the two main classes we study, the preorder of resources is mapped to a preorder of sets of resources, where the order relation is set inclusion, such that monotones can be defined via maximizing or minimizing the value of a function within these sets. In the other class, the preorder of resources is mapped to a preorder of tuples of resources, and one pulls back monotones that measure the amount of distinguishability of the different elements of the tuple (hence its information content). Monotones based on contractions arise naturally in the latter class, and, more surprisingly, so do weight and robustness measures. In addition to capturing many standard monotone constructions, our scheme also suggests significant generalizations of these. […]


    Published on August 9, 2023
    Completeness of the ZH-calculus


    There are various gate sets used for describing quantum computation. A particularly popular one consists of Clifford gates and arbitrary single-qubit phase gates. Computations in this gate set can be elegantly described by the ZX-calculus, a graphical language for a class of string diagrams describing linear maps between qubits. The ZX-calculus has proven useful in a variety of areas of quantum information, but is less suitable for reasoning about operations outside its natural gate set such as multi-linear Boolean operations like the Toffoli gate. In this paper we study the ZH-calculus, an alternative graphical language of string diagrams that does allow straightforward encoding of Toffoli gates and other more complicated Boolean logic circuits. We find a set of simple rewrite rules for this calculus and show it is complete with respect to matrices over $\mathbb{Z}[\frac12]$, which correspond to the approximately universal Toffoli+Hadamard gateset. Furthermore, we construct an extended version of the ZH-calculus that is complete with respect to matrices over any ring $R$ where $1+1$ is not a zero-divisor.


    Published on July 12, 2023