FPRD LabShare an approach

← Claims

Theorem and automata lower bounds

FPRD-T87

Linear exposed-word lower bounds for bounded periods

Exact statement

Let Σ3={0,1,2}\Sigma_3=\{0,1,2\}, B≥2B\ge2, n=⌊log⁡2((B+2)/2)⌋n=\lfloor\log_2((B+2)/2)\rfloor, and (m=2^n). There are words (U_x,V_y), indexed by x,y∈{0,1}nx,y\in\{0,1\}^n, with (|U_xV_y|=B+1) and UxVy∈SmallPer⁡BU_xV_y\in\operatorname{SmallPer}_B exactly when x≠yx\ne y. Hence nsc⁡(Bad⁡B)≥m>(B+2)/4\operatorname{nsc}(\operatorname{Bad}_B)\ge m>(B+2)/4, and every DFA for either polarity has at least (m) states. For an NFA with state set (Q) recognizing SmallPer⁡B\operatorname{SmallPer}_B, this cut proves only m≤(∣Q∣⌊∣Q∣/2⌋)m\le\binom{|Q|}{\lfloor|Q|/2\rfloor}.

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

Context

A recursive ternary code turns equality of binary labels into absence of every period through B. Reversing the acceptance polarity changes which automata lower-bound argument is valid.

Hypotheses and scope

  • Recognition is exact over the full ternary exposed-word language, not relative to a promise.
  • Every selector word has length B+1, so every tested period through B is nonvacuous.
  • The parameter m is linear in B up to a factor below four; it is not exponential in B.

Proof or evidence

The recursive code is injective and its sibling codewords are mutually cross-bifix-free with disjoint proper-period sets. A first differing label bit creates an off-diagonal border, while a three-range argument excludes every diagonal border. This gives an identity matrix for Bad_B and the standard NFA fooling set; the complementary matrix for SmallPer_B supports only a reachable-set antichain argument.

All-cap period selectors →

Verification notes

A hostile independent audit rederived both the recursive-code invariants and all-B separator interpolation, checked the n=1 and long-separator regimes, corrected the NFA polarity, and replayed the committed finite certificate and checker.

Limitations

  • The theorem concerns an already exposed word and does not lower-bound the input language of the originating transducer problem.
  • It does not realize legal runs or inversions, project through nondeterministic guessing, or prove a two-way-to-one-way conversion lower bound.
  • It does not establish alphabet, length, or state minimality and supplies no matching exact-NFA upper bound for SmallPer_B.
  • No novelty or external-review claim is made.

Open work

Determine whether a legal successful-run or inversion construction can expose this selector family without destroying the state lower bound.

Notes

The analytic recursive-code and sibling-invariant proof establishes the theorem for the full exposed-word languages over one fixed ternary alphabet; the finite certificate only corroborates bounded regimes. The Bad_B matrix has the identity polarity required by the standard NFA fooling-set argument. The SmallPer_B matrix has J-I polarity and gives only the stated Sperner antichain inequality, not an m-state NFA lower bound, matching upper bound, or exact complexity classification. Here m=Theta(B), not exponential in B. FPRD-T86 supplies complementary exposed-word DFA-upper-bound context, not a proof premise. This result does not lower-bound the source input language D_A, realize legal successful runs or inversions, project through their guessing, prove a two-way-to-one-way conversion or source-device-size lower bound, improve the source decision bounds, establish alphabet/length/state minimality, solve Automata Exchange 22.08, or support a novelty claim.