Theorem · exact impossibility classification

FPRD-SH-T10

Weak unary synchronization never restores a left quotient

Exact statement

For every m,n≥1m,n\ge1, the backward-receipt prefix automaton of (am)∗⨿{a}w(an)∗(a^m)^*\mathbin{\amalg^w_{\{a\}}}(a^n)^* is not a left-invariant quotient of its weak location automaton.

StatusAll-length determinization-orbit proof with exceptional-case audit
External reviewNo documented external or specialist review of these FPRD results is recorded.

Context

The backward receipt repairs the ordinary state quotient but cannot erase the two one-sided location boundaries in a left-compatible way.

Proof or evidence

After saturation, the prefix subset orbit is fixed, while the location subset orbit retains one left boundary and one right boundary and has least period lcm⁡(m,n)\operatorname{lcm}(m,n). At (1,1)(1,1), where that period is one, the location orbit still has one additional transient subset.

Verification notes

Complete subset orbits match the formulas for all 256 pairs with 1≤m,n≤16; an independent implementation confirms the exceptional (1,1) transient and exhaustive partition search finds no left quotient in the three smallest boundary cases.

Limitations

  • The obstruction concerns this location/prefix pair, not every automaton recognizing the same language.
  • No external review or priority claim is recorded.

Open work

Test eventual subset-period mismatch as an obstruction for non-unary synchronized products.