CS Paper Radar

Does Merge Form a Hopf Algebra? Coproducts, Traces, and the Prospects of Algebraic Minimalism

Daisuke Bekki

cs.CL math.QA ·submitted 2026-11-08 17:01 UTC · v1
theoryunusual

Abstract

Marcolli, Chomsky, and Berwick (2025; henceforth MCB) formulate the Merge operation of Minimalism on a Hopf algebra of Connes-Kreimer type, and claim that language and physics obey the same algebraic structure. This paper separates their program into the working hypothesis H, that Merge on workspaces can be described as a Hopf algebra, and the claim P placed on top of it, that language and physics obey the same principle, and examines the validity of H. MCB employs two coproducts in formulating Merge, corresponding to two different translations of movement (Internal Merge): $Δ_d$, which deletes the lower copy, and $Δ_c$, which leaves a trace. MCB uses the former in syntax and the latter at the syntax-semantics interface, but $Δ_d$ is not coassociative, and $Δ_c$ is not connected under the gradings MCB gives and, moreover, not coassociative as long as the labels of traces are retained. Consequently, MCB's algebra is not a Hopf algebra, and the Birkhoff factorization is not a consequence of the Hopf-algebra theorem but of a weaker statement that requires neither coassociativity nor connectedness. There are four ways to recover a Hopf algebra, but none of them can distinguish different traces, and hence none is compatible with Heim-Kratzer-style formal semantics, which reads traces as indexed variables. Thus H does not hold at present, and under the current formulation, making Minimalism a Hopf algebra and preserving its connection with formal semantics are mutually exclusive. Finally, we indicate three directions in which algebraic Minimalism may proceed.

Comment
15 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Hochschild Cocycle and Universality of Merge

cs.CL math.RA ·2026-11-15 ·Matilde Marcolli, Elizabeth Xiao
similarity 0.70
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 new method for proving confluence on abstract reduction systems --- Confluence of non-E-overlapping weakly-shallow TRSs ---

cs.LO ·2026-10-07 ·Masahiko Sakai, Mizuhito Ogawa, Michio Oyamaguchi
similarity 0.53
Abstract · 68 pages, 17 figures

This paper proposes a new method for proving the confluence of an abstract reduction system (ARS) by clarifying the sufficient conditions, called compatibility and edge commutativity, for expanding a given finite sub-ARS into a confluent one by adding rewrite edges. This method can be regarded as an extension of our earlier work, which showed that a weakly non-overlapping, shallow, and non-collapsing term rewriting system (TRS) is confluent. Furthermore, we apply our method to demonstrate that a non-$E$-overlapping and weakly shallow TRS is confluent. Here, a term is weakly shallow if each defined function symbol occurs either at the root or in the ground subterms, and a TRS is weakly shallow if both sides of all its rewrite rules are weakly shallow. This drops the non-collapsing condition assumed in our previous work on weakly shallow TRSs. Moreover, since a weakly shallow TRS is non-$E$-overlapping whenever it is non-$ω$-overlapping, and the latter property is decidable, we also obtain a decidable sufficient condition for confluence: non-$ω$-overlapping and weakly shallow TRSs are confluent.

0.34

Step Recursion: Mixed Stride Spectra, Path Factorization, and Synchronization Geometry

cs.CC cs.LO ·2026-08-27 ·Kirill Osipov
theory similarity 0.52
Abstract

Step recursion allows recursive computation to move through a canonical hierarchy in jumps, or strides. Suppose a function algebra is allowed to use several primitive stride lengths $L$. Composition immediately produces sums of these lengths, but it is not clear whether arbitrary nesting of mixed recursions can create any genuinely new canonical stride. We prove that it cannot: at every fixed canonical row $n\ge2$ and lower basis $m<n$, the canonical strides definable from $L$ are exactly the additive monoid $\langle L\rangle$ generated by $L$. The proof gives more information than membership alone. Every sufficiently high dependency path computing a canonical descent of stride $p$ carries total label weight exactly $p$, and the possible path signatures are precisely the additive factorizations of $p$ by the primitive stride labels. Thus the computation remembers both which strides are definable and how each one can be assembled. After saturation, inclusion between mixed-stride classes is exactly inclusion between their additive stride monoids, giving a concrete lattice description and finite certificates for inclusion. We then study several synchronized recursion clocks. Joint descent maps can encode arbitrary additive submonoids of $\mathbb N^r$, already giving continuum order complexity for $r=2$. Ordinary scalar observation, however, forgets correlations between the clocks and retains only the independent coordinate strides. This identifies precisely where synchronization information is preserved and where it collapses.

0.43

On the semantics of conditional branching

cs.LO cs.PL ·2026-11-19 ·Fredrik Dahlqvist
similarity 0.51
Abstract · 31 pages, proofs in the Appendix

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.

0.44

Restricted Peirce's Law and Natural Deduction

cs.LO ·2026-10-29 ·Satoru Niki
publishedtheoryhot direction similarity 0.49
Abstract · In Proceedings NCL'26, arXiv:2610.34489

The constructive logic JP' is known to be the weakest logic between intuitionistic and minimal logic that satisfies Glivenko's theorem. In spite of this natural and desirable formal property, the motivation for its notion of negation remains rather elusive: it can be characterised by a restriction of Peirce's law or by the double negation of ex falso quodlibet, neither of which is very intuitive. In order to have an alternative perspective on this negation, we study in this paper a couple of natural deduction systems for JP'. We first present a system that is normalisable and satisfies a restricted form of the subformula property. Then a modification of this system is introduced, whose rules satisfy the separation of connectives and the full subformula property. Afterwards we turn our attention to a typed lambda-calculus, with respect to which our natural deduction enjoys the Curry-Howard correspondence, followed by a concluding discussion.

0.40

A Theory of a Two-Dimensional Typed Lambda Calculus

cs.LO ·2026-09-16 ·Daniel O. Martínez-Rivillas, Arthur F. Ramos, Ruy J. G. B. de Queiroz
similarity 0.49
Abstract

We present a typed two-dimensional $λ$-calculus whose equality evidence is \emph{computational}: a path between two terms is an explicit finite sequence of one-step conversions (the $β$- and $η$-contractions, the congruences, and the structural rules), and every property of paths is proved \emph{by recursion over that sequence}, with any step as a base case --- in deliberate contrast with Martin-Löf type theory, where identity is generated by reflexivity alone and all properties go through the non-computational $J$-eliminator. The higher structure is imported from the $2β$- and $2η$-conversions of the theory of an arbitrary higher $λ$-model: we obtain 2-dimensional coherence laws, computable naturality of homotopies (via inductive homotopies and their explicit evaluations), a 2-dimensional path type with transport, and a parity invariant that proves the system consistent and \emph{really intensional}: the $β$- and $η$-contractions are provably distinct evidence, while in the native syntax of Idris (core MLTT) they are identified by definitional equality. Commutative diagrams accompany the main constructions, and the theory is fully formalized in Idris 2. A parallel Lean formalization is published in the Palomar registry \cite{palomar2026lean}. A philosophical reading closes the paper: constructivism in the BHK sense, proof-relevant intensionality, and the boundary between syntax and semantics, drawn relative to MLTT and HoTT.}

0.34

Hereditary permutations for simple types revisited: A baby case for University Algebra

cs.LO cs.PL ·2026-11-19 ·Thorsten Altenkirch
theory similarity 0.48
Abstract

It is a classical result that the definable isomorphisms of the simply typed lambda-calculus with function types are exactly the hereditary permutations, and that they are generated by $A \to B \to C \cong B \to A \to C$ and congruence. We give a new proof of this result that stays inside beta-normal eta-long typed terms and uses no completeness theorem: an induction that descends through both components of an isomorphism at once. We then go one level up and prove a coherence theorem: two derivations of an isomorphism denote the same isomorphism if and only if they are equal modulo an explicit list of equations (groupoid laws, functoriality, involution, naturality and the braid equation), so these equations present the groupoid of isomorphisms, a hereditary version of the Coxeter presentation of the symmetric groups. All results are formalised in Agda, on intrinsically typed syntax with hereditary substitution, without postulates. The work is a case study for the syntactic completeness conjecture of University Algebra, a proposed solution of Tarski's high school algebra problem using dependent types, whose semantic counterpart is open. We explain the motivation and which parts of the method we expect to carry over.

0.28

Dilatations of categories, via their lean formalization

cs.LO math.CT ·2026-08-10 ·Arnaud Mayeux
similarity 0.48
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