Generative Rewriting Algebra: Axioms, Probabilistic Models, and Experimental Validation in a Simulated Cognitive Agent

We introduce Generative Rewriting Algebra (GAP)—an axiomaticframework for memory organization capable of autonomous conceptformation. GAP defines a space of generative elements, a hypothesisoperator, a generative semantics, and a single variational principle: thesystem rewrites subsets of its memory into new elements when doing soreduces a total description cost. We present Symbolic GAP (S-GAP)—a concrete, discrete, and strictly lossless model that satisfies all GAPaxioms. S-GAP operates on multisets of strings and builds a hierarchicaldictionary of abstractions through greedy detection of repeated substrings.We prove that S-GAP induces an incremental Straight-Line Grammarconstruction, that its rewriting process preserves information, and that itterminates after a finite number of steps. We then generalize to ProbabilisticGAP (P-GAP) and its canonical instantiation ExponentialGAP (E-GAP) using exponential families, establishing the informationprojection theorem as the probabilistic hypothesis operator. Finally,we validate E-GAP experimentally in ACA-1—a simulated cognitiveagent with bounded active memory, noisy sensors, and survival-drivendecision-making. ACA-1 autonomously forms hierarchical Gaussian concepts,compresses active memory via phase transitions, and achieves 65%survival over 3,000 timesteps. The experimental results provide empiricalevidence consistent with the theoretical predictions of GAP, demonstratingthat the framework offers a viable foundation for autonomous conceptformation in resource-constrained cognitive systems