CS Paper Radar

Structural Morphisms for Nested Conditions - Full Version

Arend Rensink, Andrea Corradini

cs.LO ·submitted 2026-08-12 14:20 UTC · v1
published

Abstract

Nested conditions are used, among other things, as a graphical way to express first order formulas ruling the applicability of a graph transformation rule to a given match. In this paper, we first introduce several operators on conditions mimicking logical connectives. Next we propose an original notion of structural morphism among nested conditions, and we identify circumstances under which morphisms are consistent with the entailment of the corresponding conditions. Finally we frame the results in a categorical context, proving functoriality and universality properties of the various operations.

Comment
This is the full version (including proofs) of the paper published in GCM 2026

Closest papers

Nearest neighbours by meaning across the whole index.

Notation3: Graph Terms for RDF

cs.LO cs.AI ·2026-10-22 ·Dörthe Arndt, Pierre-Antoine Champin
similarity 0.66
Abstract · Submitted to TGDK

Notation3 Logic was introduced as an extension of RDF allowing the user to express rules on top of triples and to make statements about graphs. The original proposal of the logic only came with an informal specification of its semantics which has been refined later on. While this refinement clarified the meaning of rules and implicitly quantified variables, it left the meaning of graphs used as terms - so-called graph terms - open. In this paper we aim to close this gap. We discuss in detail, how graph terms are used in Notation3, which formal requirements they need to meet, and provide examples to illustrate the difficulties when defining their semantics. We then introduce an abstract syntax for the logic and define its semantics in two steps: similarly to RDF's simple interpretations, we define interpretations and basic entailment for Notation3 which covers plain RDF triples but also triples containing graph terms. N3-entailment is then an extension of basic entailment which assigns meaning to the different special predicates of the logic like for example the implication symbol. N3-entailment is defined in a way that it can be extended whenever a new predicate is added to the logic. As Notation3 Logic is currently under development, we expect many predicates to be added. Our research provides and important step towards the full standardisation of the logic.

0.24

How to prove equations using diagrams: A categorical and operational semantics for e-graphs

cs.LO math.CT ·2026-11-04 ·Evan Patterson
similarity 0.61
Abstract

E-graphs are a powerful algorithmic technique for automated equational reasoning but have resisted a conceptual understanding independent of issues of presentation and implementation. We propose an operational semantics for e-graphs based on the fundamental category-theoretic concepts of diagrams, limits, and initial functors. We illustrate the formalism through numerous example calculations and establish its soundness and completeness. Technical prerequisites are kept to a minimum in the main text; less standard elements of the mathematical theory are developed in two appendices.

0.25

Freely Generated Categorical Structures and Automatic Differentiation, PhD Thesis (Introduction and Conclusion)

cs.PL cs.LOmath.CT ·2026-09-30 ·Fernando Lucatelli Nunes
similarity 0.60
Abstract · PhD thesis, Utrecht University, 2026. Introduction, conclusion, and English and Dutch summaries only; the six research papers constituting C…

This version contains the introduction and conclusion of my PhD thesis, "Freely Generated Categorical Structures and Automatic Differentiation", together with its English and Dutch summaries. The full thesis consists of an introductory chapter, six joint research papers, and a concluding chapter, developed during my PhD studies at Utrecht University under the supervision of Gabriele Keller and Matthijs Vákár. The research papers are available separately and are not reproduced here. The introduction presents the scope of the thesis, explains the contributions of the six papers and their connections, and introduces the categorical foundations of our approach. The guiding idea is that programming languages, viewed as freely generated categorical structures, provide a principled setting for constructing structure-preserving program transformations and proving their correctness. Automatic differentiation supplies the central application: we study forward- and reverse-mode differentiation for expressive typed languages, including higher-order functions, recursive types, iteration and partiality. The semantic requirements of these transformations also motivate independent mathematical results on free distributive and extensive categories, cartesian closedness, and Grothendieck constructions. The conclusion brings these contributions together, discusses their limitations, and outlines further directions. Throughout, the thesis develops a dialogue between theory and practice: categorical semantics guides the construction of reliable and practically useful program transformations, while the demands of computation lead to new categorical structures and results.

0.22

A Fibrational Framework For Multi-Conclusion Logics

cs.LO math.LO ·2026-10-27 ·Oualid Merzouga
theory similarity 0.60
Abstract

The fibrational framework of Licata, Shulman, and Riley gives a uniform account of substructural and modal logics for single-conclusion judgments. This thesis extends it to a multiple-output setting in which cartesian resources may be used freely, while linear resources occur exactly once on either side of the turnstile. Judgments are indexed by descriptors: directed acyclic graphs generalizing the tree-shaped expressions of the original framework. Descriptor $2$-cells encode structural transformations, and explicit gates provide weakening, contraction, coweakening, and cocontraction at linear modes. We define a sequent calculus generated by two connectives, $F$ and $U$. We prove identity, invertibility, and cut admissibility. The mode and type theories present linear-non-linear $2$-polycategories, and the projection is a local discrete fibration and a fibration, with opcartesian lifts for one-output base morphisms. Two adequacy results validate the framework: its cartesian fragment recovers the Licata--Shulman--Riley calculus, and its purely linear fragment presents classical multiplicative linear logic. Finally, we relate indexed and fibrational semantics. After developing representability correspondences for multicategories and polycategories, we establish an equivalence between multi-indexed categories over a fixed representable base and multicategorical opfibrations over it, together with its biclosed bifibrational version. We also give a one-way construction from planar poly-indexed data to a planar polycategory.

0.33

Natural Deduction Derivations as Directed Acyclic Proof Graphs

cs.LO ·2026-10-19 ·Jonathan Chan, Aaron Stump
similarity 0.59
Abstract

In conventional natural deduction, a proof of a proposition is a derivation tree constructed out of inference rules with some number of premises and a conclusion judgement. For propositional logic, in contrast to the other connectives, the rule for disjunction elimination of $A \vee B$ involves concluding with an auxiliary formula C from $A \vdash C$ and $B \vdash C$. Not only is this asymmetry unsightly, it also introduces the need for commuting conversions across disjunction eliminations to transform between proof derivations that are morally equivalent but not $βη$-equivalent. To resolve the asymmetry, Jean-Yves Girard suggests a disjunction elimination rule with multiple conclusions A and B, but claims that "we have no way of bringing them back together". In this work, we pursue Girard's proposal using the key insight that proof derivations need not be trees, but may be directed acyclic graphs (DAGs) in general. Derivation rules are represented as nodes, premises as incoming edges, and conclusions as outgoing edges. Treating derivations as DAGs permits using the alternate rule by ensuring that the subderivations pointed at by each conclusion eventually join up at a new concluding node. Commuting conversions can then be formulated in terms of interactions with this join node. We explore ways to design a proof graph language with reduction and commutation rules such that proof simplification retains its concluding judgements, i.e. type preservation. In particular, we examine two styles of reduction rules: a local style, which only requires looking at the relevant subgraph of a whole proof but necessitates a number of extraneous constructs to satisfy type preservation; and a global style, which doesn't require all the extraneous constructs but necessitates looking at the entire proof graph as a whole.

0.23

Logical Relations on Display

cs.PL cs.LO ·2026-11-16 ·Steven Schaefer, Johnson He, Max S. New
top venue similarity 0.58
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

Type-Checking for Pattern-Based Tree Transformations

cs.FL cs.CL ·2026-10-08 ·C. Aiswarya, Sahil Mhaskar, M. Praveen
similarity 0.58
Abstract · 26 pages, 9 figures, full version of a preprint accepted at FSTTCS 2026

We introduce and study pattern-based tree transformations. As an illustrating example, consider a source pattern $(x \cdot y) + (x \cdot z)$ and a target pattern $x \cdot (y + z)$ as a pair. This source pattern matches any expression $e$ of the form $(e_1 \cdot e_2) + (e_1 \cdot e_3)$ (by substituting $x$ with $e_1$, $y$ with $e_2$, and $z$ with $e_3$) and the pair transforms it into the expression $e_1 \cdot (e_2 + e_3)$ as dictated by the target pattern. Note that in this example, the set of expressions that match the source pattern is not a regular tree language. We propose a model of tree transformations given by a finite representation of a (possibly infinite) set of such (source pattern, target pattern) pairs. The expressive power of this model comes at the cost of undecidability of checking equivalence. Nevertheless, we show that the type-checking problem is decidable for our model of pattern-based tree transformations. The type-checking problem asks whether applying a given transformation to trees having a given regular property (type) preserves the property. Our decision procedure is by a reduction to the emptiness problem of alternating tree automata.

0.30

SMTB: Fast Structure-Mapping with Tight Bounds

cs.AI ·2026-09-22 ·Daniel Weitekamp, Christopher MacLellan
similarity 0.57
Abstract

Structure-mapping forms analogies by aligning systems of relationally connected elements based on shared structure instead of surface features. We introduce a new structure-mapping algorithm: Structure-Mapping with Tight Bounds (SMTB) that is 5--15x faster than the structure-mapping engine (SME) and about 50\% better at finding mappings in large nested domains. SMTB is part of the broader Cognitive Rule Engine (CRE) project, a flexible multi-language-compatible framework with an accessible Python interface to state-of-the-art C++ implementations of core algorithms commonly used in cognitive systems such as pattern matching, planning, and structure-mapping. CRE and SMTB are designed to work with a wide range of representation choices. Unlike SME, which biases higher-order correspondences in tree-like predicate logic, SMTB maximizes relational connectivity without privileging higher-order relations. This allows SMTB to work just as well over arbitrary relational graphs as it does in tree-like domains of nested predicate logic. We discuss situations where privileging "higher-orderness" in structure-mapping can cause issues, and illustrate how SMTB avoids failure modes that SME would encounter in these situations. We also provide an evaluation comparing SMTB to SME v4 over 5845 domain pairs from the SME corpus.

0.43