# Literature survey

Complexity of `f : X → Y` as the minimum bit-cost of a sequence of overwrite
transformations `(S, y)` from a constant function, where `S` ranges over
subsets canonically induced by the structure of the type `X`, with incremental
MDL-style repair as the learning algorithm. Throughout, the key discriminator
is the **primitive object** each line of work optimizes: a program, a
hypothesis-space boundary, a canonical form, an algebraic decomposition, or
(closest to this project) a direct edit sequence on an extensional value table.

*(Prepared with web search where available; citations were checked for
author/venue/year plausibility but a few page ranges may be approximate.)*

## 1. Decision lists and MDL-based rule lists

**References.** R.L. Rivest, "Learning Decision Lists," *Machine Learning* 2,
1987. H.M. Proença & M. van Leeuwen, "Interpretable multiclass classification
by MDL-based rule lists" (CLASSY), *Information Sciences* 512, 2020. P. Clark &
T. Niblett, "The CN2 Induction Algorithm," *Machine Learning* 3(4), 1989.
W.W. Cohen, "Fast Effective Rule Induction" (RIPPER), ICML 1995.

**Primitive object.** An ordered list of (predicate, output) rules evaluated
first-match-wins; Proença & van Leeuwen add an explicit two-part MDL
codelength, greedily minimized. CN2/RIPPER build the list by sequential
covering: peel off the best rule, recurse on the remainder.

**Take.** The closest existing formalization of "outer MDL over an ordered
certificate". Our certificate with last-write-wins *is* a decision list read in
reverse, and our backward "settled-set" construction is sequential covering.
RIPPER's add-then-optimize passes are close analogues of repair+recompression.

**Differs.** Their subset language is arbitrary Boolean conjunctions over given
attributes — a fixed logical language with heuristic rule quality — not a
type-canonical family, and no cost model tied to symmetry-breaking choices.

## 2. MDL, two-part codes, Kolmogorov structure function, algorithmic statistics

**References.** J. Rissanen, "Modeling by Shortest Data Description,"
*Automatica* 14(5), 1978; *Stochastic Complexity in Statistical Inquiry*, 1989.
N. Vereshchagin & P. Vitányi, "Kolmogorov's Structure Functions and Model
Selection," *IEEE Trans. IT* 50(12), 2004. P. Gács, J. Tromp, P. Vitányi,
"Algorithmic Statistics," *IEEE Trans. IT* 47(6), 2001. P. Grünwald, *The MDL
Principle*, MIT Press, 2007.

**Primitive object.** Two-part code: model + data-given-model. The structure
function `h_x(α) = min{ log|S| : x ∈ S, K(S) ≤ α }` trades set complexity
against residual randomness.

**Take.** The deepest formal ancestor of the tradeoff "cost of structural
description vs what it explains"; frames our cost as a crude, effective,
finite-domain two-part code. The prompt's requirement that random functions get
no short certificates is exactly Kraft-validity of the model code.

**Differs.** Uncomputable/general (Kolmogorov) or statistical/parametric
(Rissanen); no type-induced subset family, no incremental algorithm.

## 3. Version spaces and version-space algebra

**References.** T. Mitchell, "Generalization as Search," *Artificial
Intelligence* 18(2), 1982. T. Lau, S. Wolfman, P. Domingos, D. Weld,
"Programming by Demonstration Using Version Space Algebra," *Machine Learning*
53, 2003. H. Hirsh, *Incremental Version-Space Merging*, Kluwer 1990.

**Primitive object.** The set of all hypotheses consistent with the data,
represented by S/G boundaries; algebraic composition of such sets.

**Take.** Candidate elimination is the classical analogue of our observation
that a *correctly predicted* example still shrinks the space of admissible
future modifications. In our formalism this version space is not stored: it is
the admissibility predicate derived on demand from the observation masks.

**Differs.** Maintains a set of hypotheses rather than a single minimum-cost
transformation sequence; consistency alone, no bit-cost objective.

## 4. Program synthesis with library learning

**References.** S. Gulwani, "Automating String Processing in Spreadsheets…"
(FlashFill), POPL 2011. K. Ellis et al., "DreamCoder: Bootstrapping Inductive
Program Synthesis with Wake-Sleep Library Learning," PLDI 2021. E. Dechter et
al., "Bootstrap Learning via Modular Concept Discovery," IJCAI 2013.

**Primitive object.** DSL programs computing `f(x)` pointwise, under an
MDL-style compression objective; DreamCoder additionally learns the library.

**Take.** The compression objective over a corpus suggests the multi-task
extension (shared structural library across functions); reuse discounts in our
cost model would play the role of library abstraction.

**Differs.** Exactly the "evaluator program" framing this project avoids: the
object searched is a program tree, not an edit sequence on the extension; no
canonical type-induced symmetry structure. Nothing found in this cluster
optimizes extensional overwrite sequences.

## 5. Group-theoretic symmetry: orbit/stabilizer, canonical forms, symmetry breaking, equivariant ML

**References.** Á. Seress, *Permutation Group Algorithms*, CUP 2003 (Schreier–
Sims). B. McKay, "Isomorph-free exhaustive generation," *J. Algorithms* 26(2),
1998; McKay & Piperno, "Practical graph isomorphism, II," *J. Symb. Comp.* 60,
2014 (nauty/Traces). J. Crawford, M. Ginsberg, E. Luks, A. Roy, "Symmetry-
breaking predicates for search problems," KR 1996. T. Cohen & M. Welling,
"Group Equivariant Convolutional Networks," ICML 2016. R. Kondor & S. Trivedi,
ICML 2018.

**Primitive object.** Stabilizer chains of coset indices; canonical
representatives via individualization–refinement; lex-leader predicates;
equivariant weight-sharing schemes.

**Take.** Structurally the closest match to our cost mechanism: stabilizer-
chain coset indices `|G_{i-1} : G_i|` are literally the "#choices" whose log we
charge; individualization steps in nauty are our symmetry-breaking choice
points. The stabilizer-refined cost model of memo §5 is exactly a priced
individualization–refinement.

**Differs (a genuine gap).** None of this literature casts coset/representative
selection as an information-theoretic *description cost of a function edit* in
a learning objective. Stabilizer chains serve membership tests; nauty serves
isomorph-free generation; lex-leader serves pruning; equivariant ML constrains
a parametric hypothesis class rather than pricing symmetry breaking.

## 6. Transformation semigroups, Krohn–Rhodes, word length

**References.** K. Krohn & J. Rhodes, "Algebraic Theory of Machines I,"
*Trans. AMS* 116, 1965. S. Even & O. Goldreich, "The Minimum-Length Generator
Sequence Problem is NP-Hard," *J. Algorithms*, 1981 (shortest generator words;
related problems PSPACE-complete). C. Brandl & H.U. Simon, "Complexity
Analysis: Transformation Monoids of Finite Automata," LATA 2015.

**Primitive object.** Transformation monoids and their decompositions; Cayley/
Schreier-graph reachability; shortest generator word for one group element.

**Take.** Our κ(f) is a weighted word metric in the monoid generated by
overwrites, and Cayley-graph distance is the unweighted baseline. The
settled-set reduction is what makes this metric computable without touching
the `|Y|^|X|`-vertex Cayley graph.

**Differs.** No prior framing found of "complexity of a function = shortest
transformation word from a constant function" with bit-weighted generators and
a learning angle. Worth an explicit novelty claim.

## 7. Combinatorial species, symmetric powers, association schemes

**References.** A. Joyal, "Une théorie combinatoire des séries formelles,"
*Adv. Math.* 42, 1981. F. Bergeron, G. Labelle, P. Leroux, *Combinatorial
Species and Tree-like Structures*, CUP 1998. E. Bannai & T. Ito, *Algebraic
Combinatorics I: Association Schemes*, 1984.

**Primitive object.** Equivariant functors on finite sets with a compositional
calculus; orbit-defined relation algebras on `X × X`.

**Take.** The right *language* for our derived-map family: multiplicity spaces
`K^n / S_n` are the symmetric-power species applied to a bare set; the line
family with its intersection pattern is naturally a coherent configuration.
Good grounding for "structure generates structure" as functor composition.

**Differs.** Purely enumerative/algebraic; never used as a cost/learning
framework. The bridge is new.

## 8. Occam learning, teaching dimension, hardness

**References.** A. Blumer, A. Ehrenfeucht, D. Haussler, M. Warmuth, "Occam's
Razor," *IPL* 24, 1987. S. Goldman & M. Kearns, "On the Complexity of
Teaching," *JCSS* 50(1), 1995. T. Hancock, T. Jiang, M. Li, J. Tromp, "Lower
Bounds on Learning Decision Lists and Trees," *Inf. & Comp.* 126(2), 1996.
V. Feldman, on hardness of two-level logic minimization, STOC 2006.

**Take.** Occam's Razor is the generalization theorem behind the outer MDL
step: a consistent hypothesis of few bits provably generalizes. Minimum
consistent decision-list/DNF problems are NP-hard, which predicts our exact
search cannot scale and motivates incremental repair as the workaround.

**Differs.** Representation-agnostic; bounds would need to be instantiated for
the structural subset family (its VC dimension is small — it is a union of a
few hundred explicitly listed atom fibers and their bounded conjunctions).

## 9. Incremental concept learning with repair / theory revision

**References.** G. Pagallo & D. Haussler, "Boolean Feature Discovery in
Empirical Learning" (FRINGE), *Machine Learning* 5, 1990. H. Hirsh 1990 (above).
B. Richards & R. Mooney, "Automated Refinement of First-Order Horn-Clause
Domain Theories" (FORTE), *Machine Learning* 19, 1995. S. Wrobel, "First Order
Theory Refinement," in *Advances in ILP*, 1996.

**Primitive object.** A logical theory hill-climbed by typed edit operators
triggered by misclassified examples.

**Take.** The closest behavioral match to incremental repair: a minimal,
structurally typed edit per inconsistent example.

**Differs.** Heuristic, no bit-cost accounting, no minimality target, edits act
on clauses (syntax) rather than semantically deduplicated subsets.

## 10. Boolean "certificate complexity" — terminology clash only

**References.** H. Buhrman & R. de Wolf, "Complexity Measures and Decision
Tree Complexity: A Survey," *TCS* 288(1), 2002.

In query complexity, a *certificate* is a partial assignment forcing `f(x)` for
one input `x`. Unrelated in substance to our global function-description
certificates; flagged to preempt confusion.

## 11. Exact-phrase searches and overall finding

Searches for "extensional transformation complexity", "structural description
length of subsets", "orbit-aware sampling" returned no on-topic hits. Closest
tangential structural-MDL work: Cook & Holder's SUBDUE (*JAIR* 1, 1994), which
compresses graphs by mined substructures — substructure mining, not
subset-overwrite certificates.

**Finding:** no located prior work treats function complexity as weighted edit
distance from a constant function via edits on type-canonical structural
subsets with explicit `log₂(#choices)` costing, combined with incremental MDL
repair. The nearest antecedents are: the Kolmogorov structure function (§2) for
the cost/sufficiency tradeoff; MDL rule lists (§1) for ordered-certificate
codelength; stabilizer chains / canonical forms (§5) for symmetry-breaking
choices as countable, log-costable steps. The synthesis of the three appears
novel.