FPRD LabShare an approach

← Claims

Theorem and information bound

FPRD-T82

Canonical congruence for bounded periods

Exact statement

For a finite nonempty alphabet (Gamma) and B≥1B\ge1, the joint syntactic congruence of operatornamePerp={w:p is a period of w}operatorname{Per}_p=\{w:p\text{ is a period of }w\}, 1≤p≤B1\le p\le B, is the weakest finite monoid congruence deciding every bounded-period predicate in arbitrary two-sided contexts. Its quotient (M_B) is computable and has a compositional cover by capped length, length-(B) prefix and suffix, and the period vector. If ∣Gamma∣≥2|Gamma|\ge2, then ∣Gamma∣B≤∣MB∣≤(B+1)(∑i=0B∣Γ∣i)22B|Gamma|^B\le|M_B|\le(B+1)(\sum_{i=0}^B|\Gamma|^i)^2 2^B, so exact generic storage is (Theta(B)) bits; for unary (Gamma), the quotient is trivial.

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

Context

The quotient retains exactly the information needed to decide every period through a fixed cap after arbitrary left and right concatenation.

Definitions

  • u≡Bvu\equiv_Bv when xuy∈Per⁡p  ⟺  xvy∈Per⁡pxuy\in\operatorname{Per}_p\iff xvy\in\operatorname{Per}_p for every (x,y) and p≤Bp\le B.
  • A finite cover stores (min⁡(∣w∣,B),pre⁡B(w),suf⁡B(w),PB(w))(\min(|w|,B),\operatorname{pre}_B(w),\operatorname{suf}_B(w),P_B(w)).

Proof or evidence

Regularity gives finite index and the kernel-factor argument gives the universal property. Cross-boundary comparisons make the explicit summary compositional. Distinct length-B words are separated by a length-B right context, giving the lower bound.

Canonical bounded-period quotient →

Verification notes

Two independent reviews rechecked the universal-property direction, short boundary cases, unary exception, and selected-word application; executable minimization reproduced the small binary and ternary quotients.

Limitations

  • The bound is for each fixed B; it does not produce one finite quotient for all periods.
  • It compresses an already exposed word and does not locate runs, loops, or inversion boundaries.
  • The Boolean period-existence predicate and the full vector of individual period predicates are different observations.

Open work

Study smaller quotients for genuinely restricted typed contexts rather than unrestricted word contexts.

Notes

The joint syntactic-congruence construction is standard automata machinery, and no novelty claim is made. The result compresses the output of an already exposed inversion; it does not locate inversion boundaries, eliminate quantification over successful runs, construct an equivalent one-way transducer, or solve Automata Exchange 22.08. Typed reachability minimization requires a category or semigroupoid of legal partial compositions; a raw reachable word set is insufficient. Unary alphabets are excluded only from the lower bound and Theta(B) conclusion because every word then has every positive period.