CS Paper Radar

Foundations of Algebraic Architecture Theory: A Rising Sea of Geometry, Transport, Comparison, and Reconstruction

Hiroyuki Nakahata

cs.SE cs.PL ·submitted 2026-09-23 10:00 UTC · v1
theory

Abstract

AI-generated software changes make it increasingly important to determine what a change preserves, where local consistency fails to extend globally, and which alternatives remain. We develop the foundations of Algebraic Architecture Theory (AAT) from Atoms, typed primitive facts, and Laws, equations that objects must satisfy. A reading specifies what counts as structure and which operations and laws to preserve. The main reconstruction theorem identifies the category of full geometries and all their structure-preserving morphisms with an independently defined category of local models, up to equivalence. Objects are recovered up to isomorphism and morphisms between fixed endpoints uniquely. The theory addresses gluing, diagnosis, transport, classification of changes, and reconstruction. From finite Atom families we construct cores closed under operations and geometries with sites and coefficients. We give conditions under which a Cech obstruction detects the existence of a global state and, through comparison with repair semantics, a global repair. We compare diagnoses and give a finite criterion for uniform invariance given computable finite data. Transport along exact changes has a universal property and commutes with base change on exact pointed pullback squares. Comparisons of routes generated from the same square, finite comparison diagram, and geometry factor into an invertible comparison and an idempotent normalization. We characterize when observations determine comparison preservation and classify compatible lifts. Encodings of lens and protocol semantics preserve and reflect laws and recover semantics-preserving morphisms. Applications classify and count operation-preserving changes and extend morphisms uniquely from finite tables. Corresponding Lean declarations are listed in the appendix.

Comment
285 pages, 4 figures. Also archived on Zenodo with the same source: https://doi.org/10.5281/zenodo.22913488

Closest papers

Nearest neighbours by meaning across the whole index.

SAGA: A Comparison Theorem for Local-to-Global Software Architecture - From Semantic Repair Cohomology to Algebraic-Geometric Descent

cs.PL ·2026-08-20 ·Hiroyuki Nakahata
theorycode/data similarity 0.62
Abstract · 42 pages, 2 figures. Version 1.0.1 (textual corrections to the Zenodo v1.0.0 deposit). Also archived on Zenodo with the full evidence bundle…

In a software architecture, each service can obey its own conventions and each handoff between adjacent services can hold, and yet a semantic inconsistency may remain that appears only on a full traversal of the system. This paper independently constructs two cohomologies measuring this gap between local and global correctness, and proves that they agree. The first construction speaks the language of repair: from the semantic repair options admitted in each local context and their equivalence relation, it generates the coefficient $M_{\mathrm{sem}}$. The second speaks the language of equations: it organizes the constraints of the architecture as a simultaneous equation system and generates the quotient coefficient $Q_E$ by its obstruction ideal. Over a selected finite cover $U$ in Algebraic Architecture Theory (AAT), which constructs software architecture as algebraic geometry, and under finitely many selection conditions matching the local data, the comparison map induces the isomorphism $H^1_{\mathrm{sem}}(U) \cong \check{H}^1(U, Q_E)$ together with a correspondence of residual classes. We call this the SAGA comparison theorem. The obstructions measured in the two languages are the same cohomology class, so semantic diagnosis and geometric computation translate into each other. Moreover, when the family of repair states satisfies the sheaf condition, a global repair exists if and only if the obstruction class vanishes on both sides. The paper presents this result in three layers: the mathematical proof; the Lean formalization status at release time; and a diagnosis in which the measurement tool ArchSig, on a real open-source microservice system, reproducibly walks the full circle from a measured nonzero obstruction to its disappearance after repair. The three layers refer to the same release identity, and each claim is connected to primary evidence.

0.38

Scenes: A Meta-Logical Algebra for Mutable State

cs.LO ·2026-09-24 ·Simon Foster, Carlos Isasa, Christian Pardillo Laursen
hot direction similarity 0.58
Abstract · Submitted to MFCS 2026, rejected. Plan to revise and resubmit elsewhere

Modelling of mutable state spaces and precisely describing how variables are manipulated in a program is a fundamental problem in compositional verification. Though we can make use of the embedded abstract syntax of a program for such analysis, this runs contrary to the shallow-embedding approach, and hampers efficient proof automation. On the other hand, lenses and prisms provide an elegant algebraic foundation for modelling state, which provide sufficient structure to provide meta-logical program analysis, but without requiring a deep embedding. Nevertheless lenses, as complex algebraic objects, cannot easily be combined, complemented, or collected in sets. In this paper we contribute an accompanying algebraic structure called the scene, which allows us to characterise the set of variables, or coordinates, in a state space. Scenes intuitively correspond to sets of lenses, but like lenses they are purely semantic algebraic objects. We demonstrate that scenes provide us with sufficient structure to characterise the lens-based meta-logical properties, like independence and equivalence. Moreover, we introduce the notion of a scene space, analogous to a vector space, which allows us to recover a set-like algebraic structure. Finally, we show how scenes allow us to characterise the free and bound variables of expressions and programs, without any need for syntax, and demonstrate their use for reasoning about programs by deriving reasoning principles for the parallel composition operator.

0.34

Proof Repair and (Co)algebra Equivalences

cs.PL ·2026-10-27 ·E. G Plante, Eric Paul, Cosmo Viola, G. A. Kavvos, Talia Ringer
code/data similarity 0.58
Abstract · 30 pages, 1 figure. Code: https://github.com/trey3p/proof-repair-coalgebra ; artifact: https://doi.org/10.5281/zenodo.XXXXXXX

Maintaining formal proofs in response to breaking changes in their dependencies is a major challenge of proof engineering. Proof repair is a kind of proof automation that lessens the burden of this challenge by automatically adapting proofs in response to those changes. While proof repair is well understood through an algorithmic lens, it has, until now, been poorly understood through a theoretical lens. We address this gap by giving the first foundational treatment of proof repair, focusing in particular on type-theoretic proof repair in response to changes in datatypes. Our key insight is that the core component of a proof repair algorithm---a ``configuration''---is exactly an algebra isomorphism. We formalize and prove this insight, answering open questions from prior work. We then take this one step further and show that, by taking the dual of this representation, we obtain proof repair over coinductive types. All of our results are formalized in Agda.

0.42

From the Transformer to a Formal Semantics of Coordinated Transformations

cs.AI cs.CLcs.LO ·2026-10-29 ·Marco Giunti, Fabrizia Giulia Garavaglia
similarity 0.57
Abstract · v1: 28 pages, 9 sections, this version incorporates revisions made after the first round of peer review

We develop a formal semantics for a general class of coordinated systems of parameterized transformations, taking the Transformer as a paradigmatic starting point but abstracting from its particular mathematical instantiation. Representational vectors receive both extensional reference and ordered intensional interpretations, while parameter structures acquire relative, second-level interpretations that determine how argument properties are preserved, replaced, or combined. This yields the notion of a transforming concept: a parameterized transformation whose numerical action is coordinated with a corresponding property-level map. We then distinguish the common algebraic-semantic core of these systems from their architecture-specific functional organization, allowing different mathematical instantiations and mechanical realizations of the same abstract system type. The framework is applied to attention heads and residual connections, providing semantic explanations that depend only on the shared algebraic-semantic core and their local functional organization and therefore generalize beyond the standard Transformer. These analyses also reveal the modularity of the framework: complex architectures can be decomposed into simpler semantically coordinated subsystems whose organization may recur across different abstract system types.

0.35

Finite-Context Semantics in Finitely Supported Structures

cs.LO cs.FLcs.PL ·2026-09-25 ·Gabriel Ciobanu
theory similarity 0.56
Abstract · 31 pages, 1 table, no figures

Semantics for systems with names and data often depends on finitely many distinguished values. The theory of finitely supported structures treats this dependence through invariance under permutations fixing a finite context. We develop this approach to semantics over arbitrary permutation groups and arbitrary infinite sets of atoms. The central difficulty is that finitely supported predicate spaces need not be complete lattices. We prove that, for predicates valued in a complete lattice with trivial atom action, every monotone finitely supported transformer nevertheless has least and greatest fixed points. These lie in the complete lattice determined by the transformer's context and coincide with the fixed points of every compatible monotone ambient extension equivariant under its stabilizer. Support-transfer bounds track dependencies through semantic constructions, while uniform finiteness yields finite convergence. For Boolean predicates, $m$ context-stabilizer orbits on the carrier suffice for convergence after at most $m$ iterations, even when the supported predicate lattice is orbit-infinite. We apply these results to automata, operational and modal semantics, abstract interpretation, and resource rewriting. Ultrahomogeneous atom structures in finite relational signatures yield finite cell representations, illustrated by an authorization monitor. The resulting account separates semantic existence, finite convergence, and effective computation.

0.31

Inference Equivalence and Quotient Coding

cs.AI cs.LG ·2026-11-16 ·Zibo Meng, Andrew C. M. Austin, Alin Achim
similarity 0.55
Abstract

Incomplete observations can admit multiple physical interpretations without making every task conclusion ambiguous. Recovering all compatible scenes is often unnecessary, whereas indiscriminate compression may change which claims are justified. We ask which distinctions among observation-compatible interpretation sets must be retained to preserve every valid conclusion of a specified task. We first define inference validity as truth across all physically compatible states and characterize it, under a closedness condition, by distances to physically realizable falsifying measurements. For a finite semantic claim family ordered by specificity, the Exact Inference Frontier forms the unique minimal antichain generating all valid claims. We then define inference equivalence between compatibility sets and construct a canonical quotient code from their frontiers. Among deterministic codes admitting exact inference decoding, it induces the coarsest partition, minimizing the number of distinguishable code values rather than storage or computation. Finally, we characterize inference errors from learned compatibility sets, derive conditions for exact inference preservation despite set errors, and evaluate an asymmetric learning surrogate under distribution shifts. On a registered finite bank, 145 compatibility sets yield 31 quotient codes with unchanged valid-claim sets. Across geometry, mechanism, and joint shifts, learned estimates exhibit different accuracy-specificity trade-offs. On 1,962 official HRSID test images, 1,913 distinct candidate sets induce only 36 seven-claim inference signatures, while a visual 3-NN baseline achieves 87.31% precision on issued claims.

0.38

An Algebraic Framework for Data Systems: Classification and Optimization of Algebraic Structures for Data Organization and Coding

cs.IT math.RA ·2026-08-31 ·Kendy Inoa
similarity 0.55
Abstract · 26 pages, 7 tables, 22 references. Presented as a poster at ICM 2026, Philadelphia, PA, USA. Revised: assumptions clarified, theorems correc…

Modern data systems are commonly studied through computational and information-theoretic methods, while their algebraic properties remain largely unexplored. This paper introduces a mathematical framework for modelling data systems using algebraic codes over finite groups, organized by an \emph{axiom signature}: each algebraic axiom of the data domain is shown to be \emph{sufficient} for a specific coding-theoretic capability, and each implication is given its precise reading (MDS parameters do not require a field; quotients require normality, not commutativity). Three types of results are presented. Proved: a Gilbert-Varshamov existence bound over arbitrary finite groups, commutative or not; explicit direct-sum codes over the elementary divisors of any finite abelian group; that transactions preserving a validity predicate form a submonoid of the full transformation monoid, which is not a group; that schema-preserving transformations form a finite group whose orbits are counted by Burnside's lemma; and that the constraint-preserving bijections of a data system form a finite group whose orbits partition the valid configurations. Demonstrated: an explicit code construction over $\mathbb{F}_5$, with known codes over $\mathbb{Z}_4$ and $(2^U,\triangle)$ cited to situate the framework. Proposed: an encoding efficiency measure Ef and an optimization functional $Φ$ with tunable weights, both evaluated at declared coding instances. Weight-independent comparison holds under componentwise dominance; in general the weight simplex decomposes into polyhedral chambers on which the induced order is constant.

0.20

Morph-Aware Computing: Compiler-Ordered Updates of Program State after Topology Changes

cs.PL ·2026-10-02 ·Yusuke Izawa, Junichiro Kadomoto
theory similarity 0.55
Abstract · 31 pages, 8 figures, 11 tables

In wireless sensor and mesh networks, modular robots, and shape-adaptive computers, computing modules attach, detach, or are replaced while the others keep running with their local state. A value computed under the old arrangement, such as a cached next hop, stays in memory but may no longer describe the current one, so a program can send to a neighbor that has left without any runtime errors. We present morph-aware computing, a programming model in which the application specifies a corrective update of such state, called a repair, and the compiler decides when it runs. In MorphLang, the repair is a Reconfigure branch next to the ordinary branches that handle sends, receives, and sensor samples. MorphC compiles MorphLang to bare-metal RISC-V and inserts a guard before every ordinary branch, so that each module repairs its state before any other branch sees a new topology. Relying on this order, MorphC also rejects sends whose target may be a literal or a value the repair does not always refresh. For a model of the code MorphC generates, we prove in Rocq that the repair precedes every later ordinary branch for any number of roles and topology changes. This shows that send-target checking is sound for a core language. On 19 MorphLang programs derived from seven network stacks, removing the repair worsens destination validity in ten of the 13 programs that declare one and never improves it. In a reduced reproduction of a released Contiki-NG defect, a callback-based version sends to a departed parent after 60 of 384 changes and the MorphLang version after none. The guards cost 12 cycles per loop in a microbenchmark, and on an FPGA the delay from each commit to the first send to the new neighbor matches RTL simulation.

0.40