Joshua Tan - Composing games into complex institutions Applied Category Theory 2023-11-09 | Plenary Talk at Applied Category Theory 2023Game theory, since its development by von Neumann and Morgenstern, has proliferated through the biological and social sciences as a powerful formalism for modeling strategic and cooperative interactions. Economics in particular has applied it to core disciplinary questions, with a keen interest in analytical modeling and the formal properties of game solutions. However, this wildly successful research agenda has obscured other promising uses of game theory. For instance, game theory has also long been recognized as a potential tool for the faithful description and detailed design of realistic social institutions. Calls for this high-fidelity or “descriptive” game theory have been heard from disciplines as diverse as international development, law, animal behavior, institutional economics, and sustainability. For example, political scientist Elinor Ostrom introduced the “action situation” framework as an empirically grounded generalization of game theory for structuring ethnographic description, and she imagined formal representations of institutions in terms of systems of linked action situations. The economist Leonid Hurwicz pursued the same conception of institutions as linked systems of games. In these approaches, the central questions about an institution may not involve its solutions but the uniqueness of its decision structure or its structural complexity relative to comparable institutions.act2023.github.ioact2023.github.io/papers/paper59.pdf
Tyler Hanks - A Compositional Framework for Convex Model Predictive Control Applied Category Theory 2023-11-10 | Talk at Applied Category Theory 2023Model-predictive control (MPC) originated in process control in chemical engineering, and it has found success in many applications, including autonomous driving, battery charging, path planning, and energy systems. MPC consists of specifying and repeatedly solving constrained optimization problems. These problems are designed to model the response of a controlled system to inputs while satisfying operating constraints and minimizing a cost function over a finite prediction horizon. The generality of MPC gives it several benefits, including the ability to incorporate constraints on a system’s state and control inputs, and increased robustness to sensor noise and/or system perturbations.act2023.github.ioact2023.github.io/papers/paper80.pdf
James Hefford - Optics for Premonoidal Categories Applied Category Theory 2023-11-10 | Talk at Applied Category Theory 2023We further the theory of optics or “circuits-with-holes” to encompass premonoidal categories: monoidal categories without the interchange law. Every premonoidal category gives rise to an effectful category (i.e. a generalised Freyd-category) given by the embedding of the monoidal subcategory of central morphisms. We introduce “pro-effectful” categories and show that optics for premonoidal categories exhibit this structure.Pro-effectful categories are the non-representable versions of effectful categories, akin to the generalisation of monoidal to promonoidal categories. We extend a classical result of Day to this setting, showing an equivalence between pro-effectful structures on a category and effectful structures on its free tight cocompletion. We also demonstrate that pro-effectful categories are equivalent to prostrong promonads.act2023.github.ioact2023.github.io/papers/paper51.pdf
Sean Tull - Active Inference in String Diagrams Applied Category Theory 2023-11-10 | Talk at Applied Category Theory 2023Full Title: Active Inference in String Diagrams: A Categorical Account of Predictive Processing and Free EnergyWe present a categorical formulation of the cognitive frameworks of Predictive Processing and Active Inference, expressed in terms of string diagrams interpreted in a monoidal category with copying and discarding. This includes diagrammatic accounts of generative models, Bayesian updating, perception, planning, active inference, and free energy. In particular we present a diagrammatic derivation of the formula for active inference via free energy minimisation, and establish a compositionality property for free energy, allowing free energy to be applied at all levels of an agent's generative model. Aside from aiming to provide a helpful graphical language for those familiar with active inference, we conversely hope that this article may provide a concise formulation and introduction to the framework. act2023.github.ioact2023.github.io/papers/paper42.pdf
David Spivak - All Concepts are Cat# Applied Category Theory 2023-11-10 | Talk at Applied Category Theory 2023We show that the double category Cat♯ of comonoids in the category of polynomial functors (previously shown by Ahman-Uustalu and Garner to be equivalent to the double category of small categories, cofunctors, and prafunctors) contains several formal settings for basic category theory, provides an elegant description of Weber’s nerve construction for generalized higher categories, and has subcategories equivalent to both the double category Org of dynamic rewiring systems and the double category PolyE of generalized polynomials in a finite limit category E. Also serving as a natural setting for categorical database theory, Cat♯ at once hosts models of a wide range of concepts from the theory and applications of polynomial functors and higher categories.act2023.github.ioact2023.github.io/papers/paper65.pdf
David Jaz Myers - Topological Quantum Gates in Homotopy Type Theory Applied Category Theory 2023-11-10 | Talk at Applied Category Theory 2023In this talk, we will propose a remarkably simple formalization of topological quantum gates in homotopy type theory as transport in a certain type family, following our paper of the same title. To understand how our formalization can be so simple — derivable from bare foundations in a matter of forty pages, a feat inconceivable in set theoretic foundations— we must first understand what a topological quantum gate is expected to be, and how a realistic class of such gates is describable in synthetic homotopy theory.act2023.github.ioact2023.github.io/papers/paper22.pdf
Rory Lucyshyn-Wright - Operads arising from base valued enriched functors Applied Category Theory 2023-11-10 | Talk at Applied Category Theory 2023Multicategories, also called operads, were introduced by Lambek in his categorical studies of logic and linguistics. Multicategories are widely used in applied category theory, as they provide a very general formalism for compositional structures; for example, see and the references therein. In this talk, we provide a general result that gives rise to a great many examples of symmetric multicategories, both new and old.act2023.github.ioact2023.github.io/papers/paper56.pdf
Caterina Puca - Obstructions To Compositionality Applied Category Theory 2023-11-10 | Talk at Applied Category Theory 2023Compositionality is at the heart of computer science and several other areas of applied category theory such as computational linguistics, categorical quantum mechanics, interpretable AI, dynamical systems, compositional game theory, and Petri nets. However, the meaning of the term seems to vary across the many different applications. This work contributes to understanding the different kinds of compositionality, and in particular, towards qualifying different kinds of compositionality.Formally, we introduce invariants of categories that we call zeroth and first homotopy posets, generalising in a precise sense the π0 and π1 of a groupoid. These posets can be used to obtain a qualitative description of how far an object is from being terminal and a morphism is from being iso. In the context of applied category theory, this formal machinery gives us a way to qualitatively describe the “failures of compositionality”, seen as failures of certain (op)lax functors to be strong, by classifying obstructions to the (op)laxators being isomorphisms.Failure of compositionality, for example for the interpretation of a categorical syntax in a semantic universe, can both be a bad thing and a good thing, which we illustrate by respective examples in graph theory and quantum theory.act2023.github.ioact2023.github.io/papers/paper23.pdf
Matteo Capucci - Constructing triple categories of cybernetic processes Applied Category Theory 2023-11-10 | Talk at Applied Category Theory 2023We illustrate a generalized version of the Para construction which allows to systematically construct triple categories of cybernetic processes, as well as further extensions thereof to cybernetic systems. While Para works for actions in categories, our generalization works for any suitably complete 2-category and for more general notions of action (what we call ‘oplax dependent actegories’). To exemplify the construction, we show how applying our generalized Para to the self-action of a monoidal double category of lenses and charts produces a triple category of parametric lenses, lenses and charts which improves on Spivak and Shapiro’s Org.act2023.github.ioact2023.github.io/papers/paper58.pdf
Matthew Di Meglio - Bypassing Solèr s Theorem Applied Category Theory 2023-11-10 | Talk at Applied Category Theory 2023Full title: Bypassing Solèr’s Theorem: The Key to Axiomatising DaggerCategories of Finite-Dimensional Hilbert Spacesmdimeglio.github.io/talks/ACT2023-Bypassing_Soler-Handout.pdfact2023.github.ioact2023.github.io/papers/paper18.pdf
Toby St Clere Smithe - Approximate Inference via Fibrations of Statistical Games Applied Category Theory 2023-11-10 | Talk at Applied Category Theory 2023We characterize a number of well known systems of approximate inference as loss models: lax sections of 2-fibrations of statistical games, constructed by attaching internally-defined loss functions to Bayesian lenses. Our examples include the relative entropy, which constitutes a strict section, and whose chain rule is formalized by the horizontal composition of the 2-fibration. In order to capture this compositional structure, we first introduce the notion of ‘copy-composition’, alongside corresponding bicategories through which the composition of copy-discard categories factorizes. These bicategories are a variant of the Copara construction, and so we additionally introduce coparameterized Bayesian lenses, proving that coparameterized Bayesian updates compose optically, as in the non-coparameterized case.act2023.github.ioact2023.github.io/papers/paper33.pdf
Richie Yeung - Completeness for arbitrary finite dimensions of ZXW calculus, a unifying calculus Applied Category Theory 2023-11-09 | Talk at Applied Category Theory 2023The ZX-calculus is a universal graphical language for qubit quantum computation, meaning that every linear map between qubits can be expressed in the ZX-calculus. Furthermore, it is a complete graphical rewrite system: any equation involving linear maps that is derivable in the Hilbert space formalism for quantum theory can also be derived in the calculus by rewriting. It has widespread usage within quantum industry and academia for a variety of tasks such as quantum circuit optimisation, error-correction, and education.The ZW-calculus is an alternative universal graphical language that is also complete for qubit quantum computing. In fact, its completeness was used to prove that the ZX-calculus is universally complete. This calculus has advanced how quantum circuits are compiled into photonic hardware architectures in the industry.Recently, by combining these two calculi, a new calculus has emerged for qubit quantum computation, the ZXW-calculus. Using this calculus, graphical-differentiation, -integration, and -exponentiation were made possible, thus enabling the development of novel techniques in the domains of quantum machine learning and quantum chemistry.Here, we generalise the ZXW-calculus to arbitrary finite dimensions, that is, to qudits. Moreover, we prove that this graphical rewrite system is complete for any finite dimension. This is the first completeness result for any universal graphical language beyond qubits. act2023.github.ioact2023.github.io/papers/paper7.pdf
Fabrizio Genovese - Using Open Games to Model Real Life Financial Services Applied Category Theory 2023-11-09 | Talk at Applied Category Theory 2023The Open Game Engine is an implementation in Haskell of Compositional Game Theory, a recasting of classical game theory in categorical terms. Whereas games were traditionally thought of as monolithic structures, Compositional Game Theory defines them as open processes that can be combined with each other in multiple ways. In practical applications, this allows for building complex models from simple parts and, most importantly, to make changes to the overall model by just changing some parts while all the rest stays fixed. This gives a noticeable advantage in that model prototypation can be fast and easily adaptableact2023.github.ioact2023.github.io/papers/paper6.pdf
Vincent Wang - Constructor Theory as Process Theory Applied Category Theory 2023-11-09 | Talk at Applied Category Theory 2023Constructor theory is a meta-theoretic approach that seeks to characterise concrete theories of physics in terms of the (im)possibility to implement certain abstract “tasks” by means of physical processes. Process theory, on the other hand, pursues analogous characterisation goals in terms of the compositional structure of said processes, concretely presented through the lens of (symmetric monoidal) category theory. In this work, we show how to formulate fundamental notions of constructor theory within the canvas of process theory. Specifically, we exploit the functorial interplay between the symmetric monoidal structure of the category of sets and relations, where the abstract tasks live, and that of symmetric monoidal categories from physics, where concrete processes can be found to implement said tasks. Through this, we answer the question of how constructor theory relates to the broader body of process-theoretic literature, and provide the impetus for future collaborative work between the fields.act2023.github.ioact2023.github.io/papers/paper27.pdf
Evan Patterson - Structured and decorated cospans from the viewpoint of double category theory Applied Category Theory 2023-11-09 | Talk at Applied Category Theory 2023Structured and decorated cospans are broadly applicable frameworks for building bicategories or double categories of open systems. We streamline and generalize these frameworks using central concepts of double category theory. We show that, under mild hypotheses, double categories of structured cospans are cocartesian (have finite double-categorical coproducts) and are equipments. The proofs are simple as they utilize appropriate double-categorical universal properties. Maps between double categories of structured cospans are studied from the same perspective. We then give a new construction of the double category of decorated cospans using the recently introduced double Grothendieck construction. Besides its conceptual value, this reconstruction leads to a natural generalization of decorated cospans, which we illustrate through an example motivated by statistical theories and other theories of processes.act2023.github.ioact2023.github.io/papers/paper2.pdf
Adjoint School Message Passing Logic for Categorical Quantum Mechanics Applied Category Theory 2023-11-09 | The Adjoint School 2023 was supported by the US National Science Foundation via grant DMS-2216871.
Adjoint School Game Comonads and Finite Model Theory Applied Category Theory 2023-11-09 | The Adjoint School 2023 was supported by the US National Science Foundation via grant DMS-2216871.
Adjoint School Concurrency in monoidal categories Applied Category Theory 2023-11-09 | The Adjoint School 2023 was supported by the US National Science Foundation via grant DMS-2216871.
Adjoint School Behavioural Metrics, Quantitative Logics, and Coalgebras Applied Category Theory 2023-11-09 | The Adjoint School 2023 was supported by the US National Science Foundation via grant DMS-2216871.
Adjoint School 2023 Presentations Applied Category Theory 2023-10-24 | Presentations given by the students of the 2023 Adjoint School. The Adjoint School 2023 was supported by the US National Science Foundation via grant DMS-2216871.
Philip Saville - Effectful semantics in 2 dimensional categories: premonoidal and Freyd bicategories Applied Category Theory 2023-10-24 | Talk at Applied Category Theory 2023Premonoidal categories and Freyd categories provide an encompassing framework for the semantics of call-by-value programming languages. Premonoidal categories are a weakening of monoidal categories in which the interchange law for the tensor product may not hold, modelling the fact that effectful programs cannot generally be re-ordered. A Freyd category is a pair of categories with the same objects: a premonoidal category of general programs, and a monoidal category of ‘effect-free’ programs which do admit re-ordering.Certain recent innovations in semantics, however, have produced models which are not categories but bicategories. Here we develop the theory to capture such examples by introducing premonoidal and Freyd structure in a bicategorical setting. The second dimension introduces new subtleties, so we verify our definitions with several examples and a correspondence theorem—between Freyd bicategories and certain actions of monoidal bicategories—which parallels the categorical framework.act2023.github.ioact2023.github.io/papers/paper76.pdf
Eli Sennesh - String Diagrams with Factorised Densities Applied Category Theory 2023-10-24 | Talk at Applied Category Theory 2023A growing body of research on probabilistic programs and causal models has highlighted the need to reason compositionally about model classes that extend directed graphical models. Both probabilistic programs and causal models define a joint probability density over a set of random variables, and exhibit sparse structure that can be used to reason about causation and conditional independence. This work builds on recent work on Markov categories of probabilistic mappings to define a category whose morphisms combine a joint density, factorized over each sample space, with a deterministic mapping from samples to return values. This is a step towards closing the gap between recent category-theoretic descriptions of probability measures, and the operational definitions of factorized densities that are commonly employed in probabilistic programming and causal inference.act2023.github.ioact2023.github.io/papers/paper60.pdf
Chiara Sarti - Posetal Diagrams for Logically Structured Semistrict Higher Categories Applied Category Theory 2023-10-24 | Talk at Applied Category Theory 2023We now have a wide range of proof assistants available for compositional reasoning in monoidal or higher categories which are free on some generating signature. However, none of these allow us to represent categorical operations such as products, equalizers, and similar logical techniques. Here we show how the foundational mathematical formalism of one such proof assistant can be generalized, replacing the conventional notion of string diagram as a geometrical entity living inside an n-cube with a posetal variant that allows exotic branching structure. We show that these generalized diagrams have richer behaviour with respect to categorical limits, and give an algorithm for computing limits in this setting, with a view towards future application in proof assistants.act2023.github.ioact2023.github.io/papers/paper77.pdf
Nathaniel Virgo - Unifilar Machines and the Adjoint Structure of Bayesian Models Applied Category Theory 2023-10-24 | Talk at Applied Category Theory 2023We apply recent work on category theoretical probability to the idea of Bayesian filtering, making use of the concept of a strongly representable Markov category. We show that there is an adjunction between ‘dynamical’ and ‘epistemic’ models of a hidden Markov process. Concepts such as Bayesian filtering and conjugate priors arise as natural consequences of this adjunction. Along the way we define a notion of unifilar machine, which is a kind of stochastic Moore machine in which the output is chosen stochastically, but the update function is deterministic given the output. Unifilar machines are useful as models of the behaviour of stochastic systems; we show that in the Kleisli category of the distribution monad there is a terminal unifilar machine, and its elements are controlled stochastic processes, mapping sequences of the input alphabet probabilistically to sequences of the output alphabet.act2023.github.ioact2023.github.io/papers/paper67.pdf
Filip Bar - Infinitesimal Models of Algebraic Theories and their Applications Applied Category Theory 2023-10-24 | Talk at Applied Category Theory 2023Differential geometry, as the name suggests, is the geometry of differentials; that is of infinitesimals. Indeed, the infinitesimal calculus as developed by Leibniz was the major tool for developing calculus and differential geometry until the beginning of 20th century. However, its major drawback was that infinitesimals eluded a formal definition until the advent of Non-Standard Analysis and Synthetic Differential Geometry (SDG); the latter only made possible due to the versatility of topos-theoretic constructions guaranteeing the existence of models [5, 7, 9, 6].act2023.github.ioact2023.github.io/papers/paper82.pdf
Matt Wilson - Polycategories of Supermaps on Monoidal Categories Applied Category Theory 2023-10-24 | Talk at Applied Category Theory 2023act2023.github.ioact2023.github.io/papers/paper34.pdf
Luke Morris - Computational Multiphysics in a Categorical Framework Applied Category Theory 2023-10-24 | Talk at Applied Category Theory 2023Decapodes.jl is a framework for encoding multiphysics equations, managing the composition of complex multiphysics systems, and automatically generating performant simulation code. A Decapode diagram is a combinatorial data structure in which nodes define physical quantities, and directed edges define the computational relationship between these quantities. A prior talk [4] focused on the theoretical aspects of encoding models. Here, we present the computational aspects from our Julia implementation: Decapodes.jl. Our goals are achieved by employing attributed C-Sets (ACSets) from Catlab.jl, specifying operadic composition patterns via Relational-Diagrams from Catlab.jl, and using differential operators from the Discrete Exterior Calculus (DEC). This talk builds off work in a manuscript under review in the Journal of Computational Sciences.act2023.github.ioact2023.github.io/papers/paper54.pdf
Jason Parker - Initial algebras for topologically enriched multi sorted algebraic theories Applied Category Theory 2023-10-24 | Talk at Applied Category Theory 2023act2023.github.ioact2023.github.io/papers/paper8.pdf
Lawrence Dunn - Syntax Monads for the Working Formal Metatheorist Applied Category Theory 2023-10-24 | Talk at Applied Category Theory 2023Formally verifying the properties of formal systems using a proof assistant requires justifying numerous minor lemmas about capture-avoiding substitution. Despite work on category-theoretic accounts of syntax and variable binding, raw, first-order representations of syntax, the kind considered by many practitioners and compiler frontends, have received relatively little attention. Therefore applications miss out on the benefits of category theory, such as the deeply attractive promise of reusing formalized infrastructural lemmas between implementations of different systems. Our Coq framework Tealeaves provides libraries of reusable infrastructure for first-order representations of variable binding, such as de Bruijn indices and locally nameless. In this paper we give a string-diagrammatic account of decorated traversable monads (DTMs), the key abstraction implemented by Tealeaves. We define DTMs as monoids of structured endofunctors before proving a representation theorem à la Kleisli.act2023.github.ioact2023.github.io/papers/paper63.pdf
Tomáš Gonda - Absolute continuity, supports, and idempotent splitting in Markov categories Applied Category Theory 2023-10-24 | Talk at Applied Category Theory 2023Consider a discrete probability distribution p on a finite set A. There is an unambiguous notion of the support of p — it is the set S of elements of A that are assigned non-zero probability by p. Given two distributions, p and q, one also says that q is absolutely continuous with respect to p, denoted q ≪ p, if every property of elements of A that holds with probability 1 according to p also holds with probability 1 according to q. If one moves beyond the discrete case, however, it is not immediately clear how to define these notions. This applies even more so in the abstract setting of Markov categories, an abstract approach to probabilistic processes and information flow of increasing popularity [2–11].act2023.github.ioact2023.github.io/papers/paper53.pdf
Zinovy Diskin - Data modeling with abstract constraints Applied Category Theory 2023-10-24 | Talk at Applied Category Theory 2023Constraints are fundamental for data modelling: they keep data integrity and ensure safety. Many constraint specification languages were developed, e.g., FOL and its fragments, the OCL (Object Constraint Language) widely used in the UML/EML software development ecosystem [7], or the diagrammatic language of lifting constraints [6] popular within the ACT community. These languages are successfully employed within their own ecosystems, but create severe interoperability problems when used in a heterogeneous environment [5]. Unification via XML solves the problem for only simple constraints and does not help when complex constraints modelling complex requirements appearing in system engineering (SE) are involved. In contrast, the Generalized Sketch Framework (GSF) can manage arbitrary constraints as soon as they have a specified scope: collection of elements over which the constraint is declared. This condition does hold for constraint languages used in the SE practice, and specifications in any of the languages above can be interpreted as generalized sketches (further just sketches).act2023.github.ioact2023.github.io/papers/paper83.pdf
Aziz Kharoof - Simplicial distributions, convex categories, and contextuality Applied Category Theory 2023-10-24 | Talk at Applied Category Theory 2023A striking phenomenon in physics, known as Bell’s nonlocality and its generalization called contextuality, can be expressed as the nonexistence of a joint probability distribution over the set of all measurements that marginalizes to the distributions of the restricted set of measurements obtained from the experiment. Such a joint distribution always exists in classical theories. In particular, a joint distribution provides a model where all measurement outcomes are assigned before the measurement takes place, and the measurement probabilities are obtained by considering all such global assignments with a certain probability. It is a celebrated result of Bell [1] that in quantum theory, the joint distribution does not always exist, i.e., there are contextual families of distributions.act2023.github.ioact2023.github.io/papers/paper13.pdf
Matthew Di Meglio - Enriched Symmetric Lenses and Enriched Bisimulations Applied Category Theory 2023-10-24 | Talk at Applied Category Theory 2023- We define the new notions of enriched symmetric lens and enriched bisimulation and show, under sufficient assumptions on the enrichment base, that both can be represented by spans of enriched asymmetric lenses. Symmetric delta lenses, bisimulations of Kripke frames, and strong and weak bisimulations of labelled transition systems may all be recovered by choosing an appropriate enrichment base. This work invites one to try to lift related ideas from modal logic and concurrency to the enriched setting, and contemplate the implications for other concrete instances such as Lawvere metric spaces.act2023.github.ioact2023.github.io/papers/paper16.pdf
Dario Stein - Overdrawing Urns with Signed Probabilities Applied Category Theory 2023-10-24 | Talk at Applied Category Theory 2023- A basic experiment in probability theory is drawing without replacement from an urn filled with multiple balls of different colours. Clearly, it is physically impossible to overdraw, that is, to draw more balls from the urn than it contains. This paper demonstrates that overdrawing does make sense mathematically, once we allow signed distributions with negative probabilities. A new (conservative) extension of the familiar hypergeometric (‘draw-and-delete’) distribution is introduced that allows draws of arbitrary sizes, including overdraws. The underlying theory makes use of the dual basis functions of the Bernstein polynomials, which play a prominent role in computer graphics. Negative probabilities are treated systematically in the framework of categorical probability and the central role of datastructures such as multisets and monads is emphasised.act2023.github.ioact2023.github.io/papers/paper71.pdf
Sean Tull - Causal models in string diagrams Applied Category Theory 2023-10-24 | Plenary Talk at Applied Category Theory 2023This is a summary of findings from recent work, available as a preprint linked in Ref. [1], that presents many aspects of causal reasoning according to the causal model framework in a string diagrammatic language, based on a generalised category-theoretic notion of a causal model.act2023.github.ioact2023.github.io/papers/paper41.pdf
Sophie Libkind - Additive Invariants of Open Petri Nets Applied Category Theory 2023-10-17 | Talk at Applied Category Theory 2023In this talk, we will classify all N-valued invariants of open Petri nets which are additive with respect to composition and monoidal product in the category of open Petri nets, OPetri. Formally, these invariants are monoidal functors OPetri → BN. The additive invariants of open Petri nets are completely determined by their values on a particular class of single-transition Petri nets. For open Petri nets whose legs are monic maps, the additive invariants are determined by their values on all single-transition Petri nets as well as transitionless Petri nets. Our results confirm a conjecture made by John Baez during the AMS 2022 Mathematical Research Communities workshop. The paper-length version is available at arxiv.org/abs/2303.01643.act2023.github.io/papers/paper46.pdfact2023.github.io
Nelson Niu - Monoidal structures on generalised polynomial categories Applied Category Theory 2023-10-17 | Talk at Applied Category Theory 2023Recently, there has been renewed interest in the theory and applications of de Paiva’s dialectica categories and their relationship to the category of polynomial functors. Both fall under the theory of generalized polynomial categories, which are free coproduct completions of free product completions of (monoidal) categories. Here we extend known monoidal structures on polynomial functors and dialectica categories to generalized polynomial categories. We highlight one such monoidal structure, an asymmetric operation generalizing composition of polynomial functors, and show that comonoids with respect to this structure correspond to categories enriched over a related free coproduct completion. Applications include modeling compositional bounds on dynamical systems.act2023.github.io/papers/paper61.pdfact2023.github.io
Benjamin Bumpus - Compositional Algorithms on Compositional Data Deciding Sheaves on Presheaves Applied Category Theory 2023-10-17 | Talk at Applied Category Theory 2023Algorithmicists are well-aware that fast dynamic programming algorithms are very often the correct choice when computing on compositional (or even recursive) graphs. Here we initiate the study of how to generalize this folklore intuition to mathematical structures writ large. We achieve this horizontal generality by adopting a categorial perspective which allows us to show that: (1) structured decompositions (a recent, abstract generalization of many graph decompositions) define Grothendieck topologies on categories of data (adhesive categories) and that (2) any computational problem which can be represented as a sheaf with respect to these topologies can be decided in linear time on classes of inputs which admit decompositions of bounded width and whose decomposition shapes have bounded feedback vertex number. This immediately leads to algorithms on objects of any C-set category; these include -- to name but a few examples -- structures such as: symmetric graphs, directed graphs, directed multigraphs, hypergraphs, directed hypergraphs, databases, simplicial complexes, circular port graphs and half-edge graphs.Thus we initiate the bridging of tools from sheaf theory, structural graph theory and parameterized complexity theory; we believe this to be a very fruitful approach for a general, algebraic theory of dynamic programming algorithms. Finally we pair our theoretical results with concrete implementations of our main algorithmic contribution in the AlgebraicJulia ecosystem. act2023.github.io/papers/paper45.pdfact2023.github.io
Guido Boccali - Bicategories of automata, automata in bicategories Applied Category Theory 2023-10-17 | Talk at Applied Category Theory 2023We study bicategories of (deterministic) automata, drawing from prior work of Katis-Sabadini-Walters, and Di Lavore-Gianola-Román-Sabadini-Sobociński, and linking their bicategories of ‘processes’ to a bicategory of Mealy machines constructed in 1974 by R. Guitart. We make clear the sense in which Guitart’s bicategory retains information about automata, proving that Mealy machines à la Guitart identify to certain Mealy machines à la K-S-W that we call fugal automata; there is a biadjunction between fugal automata and the bicategory of K-S-W. Then, we take seriously the motto that a monoidal category is just a one-object bicategory. We define categories of Mealy and Moore machines inside a bicategory B; we specialise this to various choices of B, like categories, relations, and profunctors. Interestingly enough, this approach gives a way to interpret the universal property of reachability as a Kan extension and leads to a new notion of 1- and 2-cell between Mealy and Moore automata, that we call intertwiners, related to the universal property of K-S-W bicategory.act2023.github.io/papers/paper10.pdfact2023.github.io
James Fairbanks - A compositional account of motifs, mechanisms, and dynamics in biochemical ... Applied Category Theory 2023-10-03 | Talk at Applied Category Theory 2023full title: A compositional account of motifs, mechanisms, and dynamics in biochemical regulatory networksRegulatory 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. act2023.github.io/papers/paper17.pdfact2023.github.io
Paul Wilson - Data Parallel Algorithms for String Diagrams Applied Category Theory 2023-10-03 | Talk at Applied Category Theory 2023We give parallel algorithms for string diagrams represented as structured cospans of ACSets. Specifically, we give linear (sequential) and logarithmic (parallel) time algorithms for composition, tensor product, construction of diagrams from arbitrary Σ-terms, and application of functors to diagrams. Our datastructure can represent morphisms of both the free symmetric monoidal category over an arbitrary signature as well as those with a chosen Special Frobenius structure. We show how this additional (hypergraph) structure can be used to map diagrams to diagrams of optics. This leads to a case study in which we define an algorithm for efficiently computing symbolic representations of gradient-based learners based on reverse derivatives. The work we present here is intended to be useful as a general purpose datastructure. Implementation requires only integer arrays and well-known algorithms, and is data-parallel by constuction. We therefore expect it to be applicable to a wide variety of settings, including embedded and parallel hardware and low-level languages.act2023.github.io/papers/paper32.pdfact2023.github.io
John Baez - Software for Compositional Modeling in Epidemiology Applied Category Theory 2023-10-03 | Talk at Applied Category Theory 2023Mathematical models of disease are important and widely used, but building and working with these models at scale is challenging. Many epidemiologists use “stock and flow diagrams” to describe ordinary differential equation (ODE) models of disease dynamics. In this talk we describe and demonstrate two software tools for working with such models. The first, called StockFlow, is based on category theory and written in AlgebraicJulia. The second, called ModelCollab, runs on a web browser and serves as a graphical user interface for StockFlow. Modelers often regard diagrams as an informal step toward a mathematically rigorous formulation of a model in terms of ODEs. However, stock and flow diagrams have a precise mathematical syntax. Formulating this syntax using category theory has many advantages for software, but in this talk we explain three: functorial semantics, model composition, and model stratification. act2023.github.io/papers/paper31.pdfact2023.github.io
Edward Morehouse - Fox cartesian structure for Gray monoidal double categories Applied Category Theory 2023-10-03 | Talk at Applied Category Theory 2023This talk presents some results from the article, Cartesian Gray-Monoidal Double Categories. There, the notion of a locally cubical Gray category is proposed, and it is shown that double categories with a hierarchy of their morphisms, as well as classical (locally globular) Gray categories, are instances of this construction. A one-object locally cubical Gray category is a Gray-monoidal double category, which can be endowed with braided, sylleptic, and symmetric structure, as in the globular case. Equipping a symmetric Gray-monoidal double category with Fox-cartesian structure requires compatible and coherent duplication and deletion. This necessitates the introduction of doubly-lax functors, along with multiple duplicator transformations, and coassociator and cocommutor modifications for these. Intuitively, the reason for this is that in the Gray-monoidal setting we cannot do two things at once, only one at a time, so we must impose and maintain an order on the higher-dimensional cells. An algebraic presentation of the resulting theory is rather complex due to the bureaucracy of linearizing higher-dimensional boundary constraints. Fortunately, it has a relatively simple and compelling representation in the graphical calculus of surface diagrams, which we present.act2023.github.io/papers/paper40.pdfact2023.github.io
Bryce Clarke - The Algebraic Weak Factorisation System for Delta Lenses Applied Category Theory 2023-10-02 | Plenary Talk at Applied Category Theory 2023Delta lenses are functors equipped with a suitable choice of lifts, and are used to model bidirectional transformations between systems. In this paper, we construct an algebraic weak factorisation system whose R-algebras are delta lenses. Our approach extends a semi-monad for delta lenses previously introduced by Johnson and Rosebrugh, and generalises to any suitable category equipped with an orthogonal factorisation system and an idempotent comonad. We demonstrate how the framework of an algebraic weak factorisation system provides a natural setting for understanding the lifting operation of a delta lens, and also present an explicit description of the free delta lens on a functor.act2023.github.ioact2023.github.io/papers/paper52.pdf
Mario Román - Collages of String Diagrams Applied Category Theory 2023-10-02 | Talk at Applied Category Theory 2023We introduce collages of string diagrams as a diagrammatic syntax for glueing multiple monoidal categories. Collages of string diagrams are interpreted as pointed bimodular profunctors. As the main examples of this technique, we introduce string diagrams for bimodular categories, string diagrams for functor boxes, and string diagrams for internal diagramsact2023.github.ioact2023.github.io/papers/paper43.pdf
Dorette Pronk - Double Categories Tutorial Applied Category Theory 2023-10-02 | Tutorial given at Applied Category Theory 2023https://act2023tutorials.netlify.app/act2023.github.io
Evan Patterson - Tutorial AlgebraicJulia Applied Category Theory 2023-10-02 | Tutorial given at Applied Category Theory 2023https://act2023tutorials.netlify.app/act2023.github.io
Richard Samuelson - Towards a Compositional Framework for Convex Analysis Applied Category Theory 2023-10-02 | Talk at Applied Category Theory 2023We outline a categorical framework for convex analysis based on the notion of convex bifunction, highlighting connections with categorical probability.act2023.github.ioact2023.github.io/papers/paper72.pdf
Diana Kessler - Higher Dimensional Subdiagram Matching Applied Category Theory 2023-10-02 | Talk at Applied Category Theory 2023Higher-dimensional rewriting is founded on a duality of rewrite systems and cell complexes, connecting computational mathematics to higher categories and homotopy theory: the two sides of a rewrite rule are two halves of the boundary of an (n+1)-cell, which are diagrams of n-cells. We study higher-dimensional diagram rewriting as a mechanism of computation, focusing on the matching problem for rewritable subdiagrams within the combinatorial framework of diagrammatic sets. We provide an algorithm for subdiagram matching in arbitrary dimensions, based on new results on layerings of diagrams, and derive upper bounds on its time complexity. We show that these superpolynomial bounds can be improved to polynomial bounds under certain acyclicity conditions, and that these conditions hold in general for diagrams up to dimension 3. We discuss the challenges that arise in dimension 4. act2023.github.io/papers/paper39.pdfact2023.github.io
Isaac Friend- Identifying classical and quantum Markovian causal models from generalized observation Applied Category Theory 2023-10-02 | Talk at Applied Category Theory 2023Jacobs, Kissinger, and Zanasi described causal models based on Bayesian networks as certain functors between CDU categories, which, like Markov categories, capture probabilistic maps synthetically by giving each object a “copying” map. In that categorical presentation of causal Bayesian networks, a complete common cause is pictured as a random variable being copied and then the outputs being used as inputs to multiple subsequent stochastic maps. The observational data, those generated by the composite process with no intervention, are summarized in a single joint state in a stochastic process category. Intervention on a variable is represented by a “cut” endofunctor severing the variable’s connections to its parents and then randomizing the variable, yielding a new joint state on all variables, called an “interventional distribution.” The problem of causal identification, to infer from observational data the influences of hypothetical interventions, is posed as the problem of computing from the original state the new state produced by the “cut” endofunctor.act2023.github.io/papers/paper78.pdfact2023.github.io
