FPRD LabShare an approach

← Claims

Theorem · effective finite-horizon collapse for regular sources

FPRD-T173

Regular hidden sources have an explicit finite selector horizon

Exact statement

Let A be accepted by an r-state DFA, let pi be a letter projection, and fix a family of m synchronous selectors with at most s states each. The family covers pi(A) globally if and only if it covers every accepted observed word through length r^(m+1)s^m-1. Consequently, fixed-budget selector feasibility is decidable for regular hidden sources, and every infeasible budget has an obstruction suite whose radius obeys the same explicit bound.

StatusSelf-contained finite-automaton proof with exhaustive bounded product audit
External reviewThe proof is an elementary finite-product and shortest-accepting-run argument. No external or specialist review of the FPRD formulation is recorded.

Context

T169 and T171 provide finite obstructions for arbitrary hidden source languages but no computable radius. T173 shows that regularity turns the missed-word relation for each candidate family into a finite automaton with an explicit size bound.

Hypotheses and scope

  • The hidden source A is recognized by a complete r-state DFA.
  • The projection is letter-to-letter between finite alphabets.
  • The family has m total deterministic synchronous selectors with at most s states each.

Proof or evidence

A missed-word NFA stores one nondeterministically chosen source run and, for each selector, its control together with a source-DFA run on its emitted lift. It has at most r^(m+1)s^m states and recognizes exactly pi(A) minus the union of the selected acceptance domains. A shortest accepting run is simple and therefore has length below the state bound.

Regular-source selection horizon →

Verification notes

The checker exhausts all 1,024 two-state source DFAs, 10,240 one-state family cases of widths one and two, and 262,144 two-state singleton cases. It checks 4,287,052 product transitions and directly validates 105,532 shortest missed words.

Limitations

  • The product-state horizon is uniform but need not be tight.
  • The bounded-budget decision procedure is finite rather than efficient.
  • The theorem does not cover asynchronous selectors or nonregular hidden sources.
  • It gives no effective horizon for the deterministic visibly pushdown lift used in FPRD-T168.

Open work

Use T174's effective common-stack-clock tier and T175's projection-clock dichotomy; study quantitative escape for action-erasing or structurally restricted sources.