FPRD LabShare an approach

← Claims

Mechanized normalization theorem

FPRD-T112

Finite principal covers differentiate exactly

Exact statement

If every one-symbol derivative of each basis language is supplied as a finite list-valued principal cover, then every one-symbol derivative of a finite principal cover has an exact finite cover. Moreover, every finite listed stack frontier has an exact cover over the epsilon basis with one term per listed stack.

StatusMechanically checked and internally audited
External reviewNo documented external or specialist review of this FPRD result is recorded.

Context

A principal term is a concrete stack stem followed by one basis language. Differentiating the stem is local unless it is empty, in which case the supplied derivative table expands the basis term to a finite cover.

Definitions

  • A finite cover (C) denotes ⟦C⟧=⋃(v,j)∈CvBj\llbracket C\rrbracket=\bigcup_{(v,j)\in C}vB_j.
  • The epsilon basis contains only the singleton empty stack language.

Proof or evidence

Lean proves the exact derivative of one term, extends it across finite union, verifies the epsilon derivative table, and proves exactCover membership for every finite list of stacks.

Cover normalization →

Verification notes

The source theorem endpoints, three-way stem case split, finite-union argument, epsilon calibration, checked import record, and resource-boundary note were reconciled. The earlier depth diagnosis was revised rather than promoted into a false invariant.

Limitations

  • Flattening can spend one cover term per listed stack before optional deduplication, so local access does not imply bounded width.
  • The theorem does not bound basis or control complexity, fresh allocation, or stationary canonicalization cost.
  • It proves neither a context-free-to-PEG inclusion nor a separation, and does not construct the stationary bounded-slot cover assumed by FPRD-T94.

Open work

Investigate the joint stationary tradeoff among width, basis complexity, fresh allocation, and access rather than treating derivative depth alone as an obstruction.

Notes

Lean checks exact differentiation of one term, its finite-union extension, the epsilon derivative table, and exactCover membership for every finite list of stacks. Flattening makes derivative access local but may spend frontier width: exactCover uses one term per listed stack before optional deduplication. The theorem does not bound cover width, derivative-basis or finite-control complexity, fresh allocation, or the access needed by a stationary canonicalizer. It therefore sharpens the open seam to a joint resource tradeoff and does not prove a CFL/PEL inclusion or separation, a scaffold lower bound, or a stationary bounded-slot compiler beyond the conditional FPRD-T94 interface.