CS Paper Radar

Hochschild Cocycle and Universality of Merge

Matilde Marcolli, Elizabeth Xiao

cs.CL math.RA ·submitted 2026-11-15 23:08 UTC · v1

Abstract

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.

Comment
59 pages, LaTeX

Closest papers

Nearest neighbours by meaning across the whole index.

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

cs.CL math.QA ·2026-11-08 ·Daisuke Bekki
theoryunusual similarity 0.70
Abstract · 15 pages

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.

0.29

On the semantics of conditional branching

cs.LO cs.PL ·2026-11-19 ·Fredrik Dahlqvist
similarity 0.57
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

Contributions to the hierarchy of probabilistic languages

cs.FL cs.CLmath.LOmath.PR ·2026-09-20 ·Lothar Sebastian Krapp, Remo Nitschke
similarity 0.53
Abstract

We reconsider the theory of probabilistic formal languages generated by n-gram models and by probabilistic context-free grammars (PCFGs). The expected hierarchy of probabilistic grammars is established by proving that every probabilistic language generated by an n-gram model is also generated by some PCFG, while some probabilistic languages generated by PCFGs cannot be generated by any $n$-gram model. We introduce the notion of fully connected PCFGs, namely PCFGs in Chomsky normal form where every production rule only involving non-terminals has non-zero probability. Our main result shows that any probabilistic language generated by an $n$-gram model differs from any probabilistic language generated by a fully connected PCFG. Therefore, the class of probabilistic languages generated by $n$-gram models is not a subset of the class generated by fully connected PCFGs.

0.46

An Algebraic Perspective on Operational Semantics

cs.PL ·2026-11-12 ·Eric Bond, Max New
theory similarity 0.50
Abstract

Languages with effects are typically given two independently specified semantic accounts: a denotational semantics based on (free) models, and an operational semantics defined by effect-specific reduction rules. This separation leads to two independently constructed semantic structures whose relationship must then be established a posteriori. We present a unified construction in which both denotational interpretation and operational reduction are constructed from an algebraic theory specifying the effects. We work with call-by-push-value extended by the operations of an algebraic theory. We prove equational canonicity and give a tree-based operational semantics that reduces every closed computation to a tree of operations. When the free model monad is a monadic container, we derive from it a configuration-based small-step semantics. Configurations are elements of the free model. Every step preserves the denotation. Under a condition we call affinity, every reduction terminates and at ground types computes the denotation. We instantiate the framework with state, errors, writer, and weighted and pre-convex probabilistic choice. For errors, writer and weighted choice we recover the familiar rules. For state we get a machine that runs the program from every initial state at once.

0.30

Full AFLs Closed under Nested Iterated $k$-Variate Substitution and Depth-k Storage Automata

cs.FL cs.CC ·2026-10-14 ·Tomoyuki Yamakami
similarity 0.50
Abstract · (10pt, A4, 3 figures, 13 pages) This is a preliminary report

Greibach and Ginsburg (1969) studied abstract families of languages or AFLs. A full AFL is a class of languages closed under the following operations: homomorphism, inverse homomorphism, intersection with regular languages, union, concatenation, and Kleene star. Greibach (1970) used a restricted substitution, called nested iterated substitution, to introduce the notion of super AFLs, which are full AFLs that are further closed under nested iterated substitution. The smallest super AFL was shown to be the class of all context-free languages. From this fact, we focus on Greibach's limited, univariable application of nested iterated substitution and further generalize it into k-variate. This introduces the notion of nested iterated $k$-variate substitution whose definition does not rely on "machines". Recently, a "two-tape" version of Hibbard's (1967) rewriting systems, which were later reformulated by Pighizzini and Pisoni (2014) as k-limited automata with "single" input/work tapes, has been studied under the name of depth-k storage automata. This work unearths a few characteristics of the languages recognized by those automata under a restriction known as frozen blank sensitivity in terms of full AFLs and nested iterated k-variate substitution. This will promote a further abstract treatment of those languages.

0.28

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.50
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

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

cs.CC cs.LO ·2026-08-27 ·Kirill Osipov
theory similarity 0.49
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

The category of nominal sets is locally monoidal closed

cs.LO math.CT ·2026-09-18 ·Fahimeh Bayeh, Peng Fu, Peter Selinger
published similarity 0.49
Abstract

The category Nom of nominal sets was proposed by Pitts and Gabbay as a setting for the semantics of abstract syntax with variable bindings. It is well-known that Nom is a topos, also known as the Schanuel topos, and in particular it follows that Nom is locally closed, i.e., every slice category Nom/X is cartesian-closed. In this paper, we show that Nom has a much stronger property: every monoidal (closed) structure on Nom induces a monoidal (closed) structure on all slice categories Nom/X. One monoidal closed structure of particular interest on Nom is the separated product A * B, whose right adjoint A -* B is called the separated function space. In particular, it follows that Nom is locally separatedly closed.

0.37