Dependency Elimination Test¶
Redundancy test — instantiates Generated Span Closure Design
Tests whether each generator already lies in the span of the others, dropping the redundant ones down to a minimal generating set.
A generating set can be honest about what it spans and still be wastefully large. Dependency Elimination Test attacks that waste directly: it asks, of each generator in turn, "if I removed this one, would the span shrink?" If the answer is no — because that generator is already reachable from the others — the generator is redundant and can be dropped without losing anything. Run to completion, the test prunes the set down to a minimal (irredundant) generating set: every remaining generator earns its place because removing it would lose reach. Its object of analysis is the generators themselves, not the derived elements — it edits the basis, not the expressions built from it. That focus is what separates it from the mechanisms that dedupe outputs or compare rival bases.
Example¶
A team maintains a library of data-pipeline transforms billed as the "irreducible toolkit" — filter, map, sort, dedup, group, and a top_n step that returns the largest N rows. Someone suspects top_n isn't really primitive. Dependency Elimination Test checks it: is top_n already in the span of the others under composition? It is — top_n equals sort (descending) followed by a head-style filter, both already in the set. So top_n is redundant: removing it shrinks the toolkit but not the space of pipelines the toolkit can express. The team drops it (or demotes it to a documented convenience alias) and re-runs the test on the survivors to confirm none of them has become redundant now that top_n is gone.
The result is a smaller toolkit with the same reach — every remaining transform is one you genuinely cannot build from the rest. The catalog got honest about which of its "primitives" were primitives.
How it works¶
- Pick a candidate generator. Choose one generator to test for removability.
- Ask a membership question about it. Using the span's membership criterion, test whether the candidate is reachable from the other generators alone.
- Drop if reachable. If it is in the span of the rest, mark it redundant and remove it; if not, it is load-bearing and stays.
- Iterate to a fixed set. Repeat over the remaining generators until no further removal is possible — the surviving set is minimal.
- Record the dependence map. Log which generators were removable and via what combination of the others, so the pruning is auditable.
The engine underneath is a membership test aimed inward: instead of asking whether an external target is reachable, it asks whether a generator is reachable from its peers.
Tuning parameters¶
- Removal order — which generator you test first. Because a set can have several different minimal subsets, order changes which generators survive even when the final size is the same.
- Membership rigor — how strong the reachability check must be before a generator is declared redundant. Strict checks avoid dropping a generator that was only approximately reachable; loose ones prune more aggressively.
- Keep-for-convenience threshold — whether a redundant-but-frequently-used generator is deleted or retained as a labeled alias. Retaining it trades minimality for ergonomics.
- Re-test cadence — whether the whole set is re-tested after each removal or only once. Re-testing catches newly-exposed redundancies at the cost of more checks.
When it helps, and when it misleads¶
Its strength is that it stops catalog bloat at the source: it is the mechanism that answers "do we actually need this primitive?" with evidence instead of habit, and it keeps a generating set lean enough that reasoning about it stays tractable.
Its subtle failure is order dependence: a set can admit several different minimal subsets, so which generators survive depends on the order you tested them, and two honest runs can disagree about the "right" primitives even when they agree on the count.[n1] A related misuse is over-pruning: dropping a generator that is only reachable under an approximation or a truncated closure, so the span quietly shrinks in the full space. The guarding discipline is to fix and document the removal order (or prove the structure is order-independent) and to require an exact, not approximate, membership witness before any generator is eliminated — a redundant generator should be provably rebuildable from the survivors.
How it implements the components¶
Dependency Elimination Test realizes the redundancy-side machinery, aimed at the basis:
dependence_redundancy_map— its primary output: the record of which generators are redundant and how each is rebuilt from the others.span_membership_criterion— it runs the membership test inward, asking whether a generator lies in the span of its peers.generator_set_specification— it edits the specification itself, emitting the pruned minimal generating set.
It does NOT collapse equivalent expressions built from the generators (normal_form_or_equivalence_policy) — that is Normal Form Reduction Procedure: this test removes generators, that procedure canonicalizes outputs. And it minimizes one basis rather than comparing rival ones across coverage (coverage_or_reachability_record, downstream_use_contract) — that is Basis Sensitivity Review, its nearest twin: minimize within a single set versus compare across alternative sets.
Related¶
- Instantiates: Generated Span Closure Design — the test supplies the minimal generating set and the redundancy map the appraisal relies on.
- Consumes: Span Membership Certificate supplies the inward membership check that decides whether a generator is redundant.
- Sibling mechanisms: Generator Inventory · Closure Generation Workflow · Span Membership Certificate · Normal Form Reduction Procedure · Reachability Matrix or Table · Bounded Depth Generation Template · Basis Sensitivity Review
Editorial Notes¶
Form Classification¶
Form family: Analysis, Modeling & Optimization
Rationale: The mechanism repeatedly applies a span-membership criterion to each generator and removes those algebraically reachable from the others until a minimal set remains, so its operative form is formal redundancy analysis.
Nearest alternative: Experiment, Test & Rehearsal — Candidates are called tests, but no target is physically or empirically exposed; removability is established by deterministic computation.
Review outcome: Adjudicated after independent review; high confidence.
Origin Attribution¶
Primary origin: Mathematics
Origin pattern: Single lineage
Present-day reach: Universal
Rationale: Linear algebra and matroid theory established testing whether a generator lies in the span of the others and pruning to an irredundant basis.
Review resolution: Linear algebra and matroid theory established testing whether a generator lies in the span of the others and pruning to an irredundant basis. The irredundant-basis test cohered in linear algebra and matroid theory; optimization uses do not constitute a separate origin.
Review outcome: Reconciled after independent review; high confidence.
Notes¶
[n1] A matroid abstracts the notion of independence (as in linearly independent vectors), and one of its defining guarantees is that every maximal independent set — every basis — has the same size, reached by any greedy removal order. When the structure over your generators is not a matroid, that guarantee fails: greedy elimination can land on different minimal sets depending on order, which is exactly the trap this footnote flags. ↩