FPRD LabShare an approach

FPRD-T169: Causal selection spectra and finite escape

Contents

1. Resource-bounded selector covers

Let A⊆Σ^∗A\subseteq\widehat\Sigma^* and let

π:Σ^∗→Σ∗ \pi:\widehat\Sigma^*\to\Sigma^*

be a letter-to-letter projection. A synchronous causal selector is a deterministic Mealy transducer T:Σ∗→Σ^∗T:\Sigma^*\to\widehat\Sigma^* satisfying π(T(w))=w\pi(T(w))=w for every word ww.

For positive integers m,sm,s, write

(m,s)∈Sel⁡(A,π) (m,s)\in\operatorname{Sel}(A,\pi)

when some family of at most mm selectors, each with at most ss states, covers all accepting observed words:

π(A)=⋃iTi−1(A). \pi(A)=\bigcup_i T_i^{-1}(A).

Write (m,s)∈Sel⁡n(A,π)(m,s)\in\operatorname{Sel}_n(A,\pi) when the same equality is required only on words of length at most nn.

The pair (A,π)(A,\pi), not the projected language alone, determines these sets. Different hidden presentations of the same language can have different selection requirements.

2. FPRD-T169: exact finite-horizon compactness

For every finite pair of alphabets and every (A,π)(A,\pi):

  1. each Sel⁡n(A,π)\operatorname{Sel}_n(A,\pi) is upward closed in N>02\mathbb N_{>0}^2;
  2. the horizon sets decrease: Sel⁡n+1(A,π)⊆Sel⁡n(A,π); \operatorname{Sel}_{n+1}(A,\pi) \subseteq \operatorname{Sel}_n(A,\pi);
  3. global feasibility is exactly survival at every finite horizon: Sel⁡(A,π)=⋂n≥0Sel⁡n(A,π). \operatorname{Sel}(A,\pi) =\bigcap_{n\ge 0}\operatorname{Sel}_n(A,\pi).

Proof

Upward closure follows by permitting unused selectors and unused states. Restriction from horizon n+1n+1 to horizon nn proves the decreasing law.

Fix (m,s)(m,s). Over finite input and output alphabets there are only finitely many labeled deterministic synchronous Mealy machines with at most ss states. Therefore there are only finitely many candidate families containing at most mm such machines.

Let FnF_n be the set of those candidate families that cover through horizon nn. The sets

F0⊇F1⊇F2⊇⋯ F_0\supseteq F_1\supseteq F_2\supseteq\cdots

are nested subsets of one finite universe. If (m,s)(m,s) belongs to every Sel⁡n(A,π)\operatorname{Sel}_n(A,\pi), then every FnF_n is nonempty. A nested sequence of nonempty subsets of a finite set has nonempty intersection. Any family in that intersection works on every finite word and is therefore a global accepting selector cover. The reverse implication is immediate.

3. Finite Pareto bases and escape lengths

Because Sel⁡(A,π)\operatorname{Sel}(A,\pi) is upward closed in N2\mathbb N^2, Dickson’s lemma gives it a unique finite antichain of minimal feasible pairs whenever it is nonempty.

For a resource pair outside the spectrum define its escape length by

eA,π(m,s)=min⁡{n:(m,s)∉Sel⁡n(A,π)}. e_{A,\pi}(m,s) =\min\{n:(m,s)\notin\operatorname{Sel}_n(A,\pi)\}.

T169 proves that this minimum is finite for every infeasible pair. It also shows that escape length is monotone under resource enlargement: if m′≥mm'\ge m and s′≥ss'\ge s, then a finite eA,π(m′,s′)e_{A,\pi}(m',s') cannot be smaller than eA,π(m,s)e_{A,\pi}(m,s).

The theorem is qualitative. It does not make the escape function computable from a description of AA, and it supplies no closed-form upper bound.

4. Transport consequence

FPRD-T167 maps selector resources into stationary transport resources. If

(m,s)∈Sel⁡(A,π)and(d,k,g,q)∈Tr⁡(A), (m,s)\in\operatorname{Sel}(A,\pi) \quad\text{and}\quad (d,k,g,q)\in\operatorname{Tr}(A),

then

(md,k,gm,(sq)m)∈Tr⁡(π(A)). (md,k,g^m,(sq)^m)\in\operatorname{Tr}(\pi(A)).

Thus the selection spectrum gives a finite certificate for one important positive mechanism: finitely many bounded-state online choices can be packed into one stationary presentation.

5. The hard visible lift escapes every fixed budget

FPRD-T168 gives a deterministic visibly pushdown language ACA_C with a degree-one, distance-two scaffold but with

Sel⁡(AC,π)=∅. \operatorname{Sel}(A_C,\pi)=\varnothing.

Applying T169, every fixed pair (m,s)(m,s) fails at a finite horizon:

eAC,π(m,s)<∞for all finite m,s. e_{A_C,\pi}(m,s)<\infty \qquad\text{for all finite }m,s.

This sharpens the statement that no global finite selector family exists. For every proposed finite online strategy budget, some finite observed words already defeat every strategy in that budget. The result does not identify an optimal witness length for the Kim-Park language.

6. Boundary of the statement

  • The compactness proof applies to finite-state synchronous selectors. It does not apply to arbitrary causal functions with unbounded memory.
  • An empty selection spectrum is a property of a hidden presentation. It does not by itself prove that the projected language is outside SCA or PEG.
  • The hard-lift application imports the Kim-Park SCA separation through FPRD-T168. This note does not reprove that separation or inspect its Lean artifact.
  • The finite checker below tests the nested-family identities in a bounded model. It is not a proof of the infinite compactness statement.

Finite automata, compactness over a finite candidate universe, and Dickson’s lemma are classical. The contribution here is the resource formulation and its exact connection to the stationary-transport program. No literature priority claim is made without specialist review.

Sources