CS Paper Radar

On the semantics of conditional branching

Fredrik Dahlqvist

cs.LO cs.PL ·submitted 2026-11-19 16:49 UTC · v1

Abstract

Motivated by the non-standard interpretations of if-then-else in probabilistic and quantum programs we review the different semantics of conditional branching and propose a unifying categorical structure for the interpretation of if-then-else. We show that many semantically important categories possess this structure, covering inter alia classical, probabilistic, quantum or non-deterministic computations. We examine algebraic structures related to and generated by this categorical structure, in particular on collections of predicates. In this setting we show that the skew-associativity rules of GKATs and barycentric algebras are two instances of a common skew-associativity rule.

Comment
31 pages, proofs in the Appendix

Closest papers

Nearest neighbours by meaning across the whole index.

Fibered Separation Logic: Weakest Preconditions, Universal Constructions, and Local Independence

cs.PL cs.LO ·2026-11-05 ·John M. Li, Ryan Doenges, Pedro H. Azevedo de Amorim
similarity 0.60
Abstract · 41 pages, 5 figures

This paper introduces a categorical framework for models of higher-order separation logic including the weakest precondition modality. Weakest preconditions are interpreted by strong monads on a category fibered over a model of Moggi's computational lambda calculus. The fibered categories in question are termed bunched fibrations and shown to be equivalent to BI hyperdoctrines. Well-known heuristic techniques for obtaining weakest preconditions are shown to be expressible in categorical terms and are proved sound. The ``baking in the frame rule'' trick is shown to satisfy a universal property. Constructions are given for extending a program logic with cost credits. Our largest case study is parametrized by a category having local independent product (LIP) structure, a notion due to Simpson that axiomatizes name generation, randomness, and local state. From an LIP category, we construct an allocation monad, a bunched fibration, and a monad lifting. We instantiate our construction to obtain a novel probabilistic separation logic for measure-theoretic probability that both simplifies and clarifies prior work.

0.31

Logical Relations on Display

cs.PL cs.LO ·2026-11-16 ·Steven Schaefer, Johnson He, Max S. New
top venue similarity 0.60
Abstract · 31 pages, 3 figures, to appear at POPL 2027

The metatheory of programming languages suffers from a lack of reuse. Researchers develop individual calculi and prove standard properties, but very few results are truly reused across papers. The problem is worse in proof assistants, where developments routinely duplicate code from prior work or rebuild it from scratch. Category theory provides the most promising path toward reusable programming language semantics. Universal properties capture the type connectives---products, functions, sums---together with their $β$/$η$ laws. Free categorical structures identify syntactic calculi. \emph{Displayed} categories provide a uniform language for specifying logical relations, and general theorems about fibrations allow their structure to be assembled compositionally. In this work we develop a library of formalized category theory in the Cubical Agda proof assistant directly applicable to programming language metatheory. We develop theories of universal properties and free categorical structures, apply them to define denotational semantics and logical relations for simply typed calculi, and identify encodings of the categorical constructions that make typechecking them tractable. From the same categorical components, we construct several familiar results via a logical relations construction---canonicity,parametricity,conservativity---and provide a proof of coherence for monoidal categories.

0.48

Premonoidal Semantics and Scalable Diagrammatics of Fermionic Quantum Computing

cs.LO quant-ph ·2026-10-01 ·Thomas Perez, Titouan Carette
similarity 0.59
Abstract

Local fermionic mode (LFM) based quantum computation has pure state spaces that are isomorphic, via the Jordan-Wigner representation, to qubit state spaces, but its compositional structure is subtly different. Indeed, the algebraic formalism specifying how to embed fermionic systems underlies a notion of parallel composition, for which, in general, the usual interchange law of monoidal categories fails. We give a categorical account of this phenomenon. Starting from the CAR-algebraic semantics of fermionic gate application, we show that LFM processes form a symmetric premonoidal category whose centre is precisely the even, parity-preserving subcategory. The same processes can alternatively be organized with the ordinary tensor product and a fermionic presymmetry that is natural exactly on even maps. To reason diagrammatically in this latter presentation, we introduce pronaps, a relaxation of the notion of prop, in which permutations are not-necessarily-natural, and use them to organize a hierarchy of fragments of the fermionic ZW calculus relevant to the study of fermionic circuits on physically motivated gate-sets. We then extend scalable diagrammatic notation to pronaps. In this setting, syntactic sugars inspired by SZX and GSA are defined, with the specificity that matrix arrows encode minors and determinants, while graph triangles encode pfaffians of principal submatrices. These constructions yield elegant normal forms and completeness proofs for our presentations of the EoW, FoW, EW, and FW fragments. In particular, the FW presentation gives a new normal form for the matchgate fragment, distinct from the rWGS-X normal form of the planar-W (pW) presentation of the same category. The resulting framework connects fermionic circuit semantics, diagrammatic rewriting with scalable notations, and the algebra of determinants and pfaffians.

0.25

Arrow Operations in Categories of Lattice-valued Relations

cs.DM math.CT ·2026-08-17 ·Fatemeh Jowkar, Michael Winter
similarity 0.59
Abstract

Arrow allegories provide a convenient abstract framework to work with lattice-valued relations, or more precisely, relations that use the elements of a given Heyting algebra as truth values. One characteristic of arrow allegories is that all relations of the given arrow allegory use the same Heyting algebra ${\mathcal H}$. In this paper we want to extend this approach to allegories where relations between different objects may use different lattices of truth values and even further to relations that use a different lattice of truth values for every pair in the relation. Therefore, we define three concrete allegories, $\mathrm{Rel}({\mathcal H})$, $\mathrm{Rel}^u({\mathcal H})$ and ${\mathcal H}{\rm-Rel}$, where the allegory listed later is a full suballegory of the previous ones. These three allegories capture the three different situations mentioned above. In particular, ${\mathcal H}{\rm-Rel}$ is the standard example of an arrow category. We investigate these allegories and provide suitable categorical definitions for these structures.

0.23

Logics vs doctrines, a mirror symmetry

cs.LO math.CTmath.LO ·2026-10-21 ·Ivan Di Liberti, Umberto Tarantino, Lingyuan Ye
theory similarity 0.57
Abstract · Corrected typo in title and reworded abstract

We study the relationship between doctrines, encoding 2-categories of theories in predicate logic, and fragments of geometric logic, defined through Kan injectivity in the 2-category of topoi. After a brief historical account of the notion of doctrine, we propose our working definition. Our main result then establishes a Galois connection between doctrines and subgeometric logics. This connection suggests a mirror symmetry between the world of doctrines and the world of logics, in which constructions and results on either side admit counterparts on the other. We develop this symmetry through constructions of syntactic categories and classifying topoi in both settings, recovering the familiar examples from categorical logic. We prove paired Diaconescu-type theorems and give symmetric universal characterisations of the two closure operators induced by the Galois connection. Finally, we show that passing from a doctrine to its closure induces a reflection between the corresponding 2-categories of algebras, and we relate this reflection to conceptual completeness.

0.29

Hochschild Cocycle and Universality of Merge

cs.CL math.RA ·2026-11-15 ·Matilde Marcolli, Elizabeth Xiao
similarity 0.57
Abstract · 59 pages, LaTeX

The Hopf algebra Markov chain dynamical system, on the Hopf algebra of non-planar binary forests, that models the action of Merge on workspaces in Chomsky's Minimalist Model of syntax, satisfies a universal property, determined by the fact that the Merge operation is a Hochschild 1-cocycle. This universal property has an interpretation in terms of models of the syntax-semantics interface, as it shows that, if the side of semantics possesses a sufficiently rich compositional structure, then that structure is uniquely induced by the syntactic Merge, once the semantic values of lexical items and syntactic features are assigned. We illustrate how this universality works by showing, in particular, full compatibility of this Hopf algebraic formulation with Heim-Kratzer semantics.

0.40

A Complete Equational Theory for Quantum Circuits with Generalized Control

cs.LO math.CT ·2026-11-04 ·William Schober, Scott Wesley
published similarity 0.56
Abstract · In Proceedings QPL 2026, arXiv:2611.04069

Controlled subcircuits are commonplace in quantum algorithms as they represent the quantum analogue of branching statements (if then). We introduce a generalization of controlled subcircuits in the form of a binary operation which sends pairs of unitary quantum circuits to a generalized controlled operation, whose semantics are based on matrix exponentials and logarithms. The family of quantum circuits with generalized controlled operations and circuit exponentiation is denoted HQC for Hierarchical Quantum Circuits. We formalize HQC as a modified prop category using a novel category-theoretic construction, and provide a sound and complete equational theory for diagrammatic reasoning in HQC.

0.37

Dilatations of categories, via their lean formalization

cs.LO math.CT ·2026-08-10 ·Arnaud Mayeux
similarity 0.56
Abstract

Given a category $\calC$ and a center, that is a collection of pairs $(d_i, N_i)$ consisting of a morphism $d_i$ and a sieve $N_i$ over its codomain, the dilatation of $\calC$ is a new category $\calC'$ in which every $n \in N_i$ factors, uniquely and functorially, through $d_i$. This paper presents the theory of dilatations of categories through a full formalization of the construction and its main theorems in the Lean~4 proof assistant, on top of the Mathlib library. An appendix collects a systematic dictionary between the mathematical statements and the Lean declarations that formalize them.

0.04