Home

The categorical contours of the Chomsky-Sch\"utzenberger representation theorem


We develop fibrational perspectives on context-free grammars and on nondeterministic finite-state automata over categories and operads. A generalized CFG is a functor from a free colored operad (aka multicategory) generated by a pointed finite species into an arbitrary base operad: this encompasses classical CFGs by taking the base to be a certain operad constructed from a free monoid, as an instance of a more general construction of an \emph{operad of spliced arrows} $\mathcal{W}\,\mathcal{C}$ for any category $\mathcal{C}$. A generalized NFA is a functor from an arbitrary bipointed category or pointed operad satisfying the unique lifting of factorizations and finite fiber properties: this encompasses classical word automata and tree automata without $\epsilon$-transitions, but also automata over non-free categories and operads. We show that generalized context-free and regular languages satisfy suitable generalizations of many of the usual closure properties, and in particular we give a simple conceptual proof that context-free languages are closed under intersection with regular languages. Finally, we observe that the splicing functor $\mathcal{W} : Cat \to Oper$ admits a left adjoint $\mathcal{C}: Oper \to Cat$, which we call the \emph{contour category} construction since the arrows of $\mathcal{C}\,\mathcal{O}$ have a geometric interpretation as oriented contours of operations of $\mathcal{O}$. A direct consequence of the contour / splicing adjunction is that every […]


Published on May 16, 2025
The Many-Worlds Calculus


In this paper, we explore the interaction between two monoidal structures: a multiplicative one, for the encoding of pairing, and an additive one, for the encoding of choice. We propose a colored PROP to model computation in this framework, where the choice is parameterized by an algebraic side effect: the model can support regular tests, probabilistic and non-deterministic branching, as well as quantum branching, i.e. superposition. The graphical language comes equipped with a denotational semantics based on linear applications, and an equational theory. We prove the language to be universal, and the equational theory to be complete with respect to this semantics.


Published on May 16, 2025
Ranked Enumeration of Conjunctive Query Results


We study the problem of enumerating answers of Conjunctive Queries ranked according to a given ranking function. Our main contribution is a novel algorithm with small preprocessing time, logarithmic delay, and non-trivial space usage during execution. To allow for efficient enumeration, we exploit certain properties of ranking functions that frequently occur in practice. To this end, we introduce the notions of {\em decomposable} and {\em compatible} (w.r.t. a query decomposition) ranking functions, which allow for partial aggregation of tuple scores in order to efficiently enumerate the output. We complement the algorithmic results with lower bounds that justify why restrictions on the structure of ranking functions are necessary. Our results extend and improve upon a long line of work that has studied ranked enumeration from both a theoretical and practical perspective.


Published on May 16, 2025
Drawing with Distance
Authors: Bart Jacobs.


Drawing (a multiset of) coloured balls from an urn is one of the most basic models in discrete probability theory. Three modes of drawing are commonly distinguished: multinomial (draw-replace), hypergeometric (draw-delete), and Polya (draw-add). These drawing operations are represented as maps from urns to distributions over multisets of draws. The set of urns is a metric space via the Kantorovich distance. The set of distributions over draws is also a metric space, using Kantorovich-over-Kantorovich. It is shown that these three draw operations are all isometries, that is, they exactly preserve the Kantorovich distances. Further, drawing is studied in the limit, both for large urns and for large draws. First it is shown that, as the urn size increases, the Kantorovich distances go to zero between hypergeometric and multinomial draws, and also between P\'olya and multinomial draws. Second, it is shown that, as the drawsize increases, the Kantorovich distance goes to zero (in probability) between an urn and (normalised) multinomial draws from the urn. These results are known, but here, they are formulated in a novel metric manner as limits of Kantorovich distances. We call these two limit results the law of large urns and the law of large draws.


Published on April 30, 2025
String Diagrams for Premonoidal Categories


Premonoidal categories are monoidal categories without the interchange law while effectful categories are premonoidal categories with a chosen monoidal subcategory of interchanging morphisms. In the same sense that string diagrams, pioneered by Joyal and Street, are an internal language for monoidal categories, we show that string diagrams with an added "runtime object", pioneered by Alan Jeffrey, are an internal language for effectful categories and can be used as string diagrams for effectful, premonoidal, and Freyd categories.


Published on April 29, 2025

Managing Editors

 

Stefan Milius
Editor-in-Chief

Brigitte Pientka
Fabio Zanasi
Executive Editors


Editorial Board
Executive Board
Publisher

eISSN: 1860-5974


Logical Methods in Computer Science is an open-access journal, covered by SCOPUS, DBLPWeb of Science, Mathematical Reviews and Zentralblatt. The journal is a member of the Free Journal Network. All journal content is licensed under a Creative Commons license.