Generative Rewriting Algebra: An Axiomatic Framework and Its Canonical Symbolic Model

We introduce Generative Rewriting Algebra (GAP) — an axiomatic framework for memory organization capable of autonomous concept formation. GAP defines a space of generative elements, a hypothesis operator, a generative semantics, and a single variational principle: the system rewrites subsets of its memory into new elements when doing so reduces a total description cost. We then present Symbolic GAP (S-GAP) — a concrete, discrete, and strictly lossless model that satisfies all GAP axioms. S-GAP operates on multisets of strings and builds a hierarchical dictionary of abstractions through greedy detection of repeated substrings. We prove that S-GAP is equivalent to Straight-Line Grammar compression, that its rewriting process preserves information, and that it terminates after a finite number of steps. S-GAP serves as a canonical toy model for the broader GAP framework, which is designed to be realized by more complex (probabilistic, continuous) systems including exponential families, kernel embeddings, and neural generative models.