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.

To appear.

  • Manin and Marcolli. Homotopy Theoretic and Categorical Models of Neural Information Networks (arXiv).
  • Gonda, Reinhart, Stengele, and De les Coves. A Framework for Universality in Physics, Computer Science, and Beyond (arXiv).

Recently published

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
Koszul duality for operadic categories

The aim of this sequel to arXiv:1812.02935 is to set up the cornerstones of Koszul duality and Koszulity in the context of operads over a large class of operadic categories. In particular, for these operadic categories we will study concrete examples of binary quadratic operads, describe their Koszul duals and prove that they are Koszul. This includes operads whose algebras are the most important operad- and PROP-like structures such as the classical operads, their variants such as cyclic, modular or wheeled operads, and also diverse versions of PROPs such as properads, dioperads, 1/2PROPs, and still more exotic objects such as permutads and pre-permutads.

Published on June 16, 2023
Operadic categories as a natural environment for Koszul duality

This is the first paper of a series which aims to set up the cornerstones of Koszul duality for operads over operadic categories. To this end we single out additional properties of operadic categories under which the theory of quadratic operads and their Koszulity can be developped, parallel to the traditional one by Ginzburg and Kapranov. We then investigate how these extra properties interact with discrete operadic (op)fibrations, which we use as a powerful tool to construct new operadic categories from old ones. We pay particular attention to the operadic category of graphs, giving a full description of this category (and its variants) as an operadic category, and proving that it satisfies all the additional properties. Our present work provides an answer to a question formulated in Loday's last talk in 2012:``What encodes types of operads?''. In the second and third papers of our series we continue Loday's program by answering his second question: ``How to construct Koszul duals to these objects?'', and proving Koszulity of some of the most relevant operads.

Published on June 5, 2023