FPRD LabShare an approach

FPRD-T167 and FPRD-T168: Finite causal selector covers

Contents

1. Hidden histories and causal selectors

Let A⊆Σ^∗A\subseteq\widehat\Sigma^* be a language over a tagged alphabet 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 ww. It chooses one complete hidden history online.

A family T1,…,TmT_1,\ldots,T_m is an accepting selector cover for (A,π)(A,\pi) when

π(A)=⋃i=1mTi−1(A). \pi(A)=\bigcup_{i=1}^m T_i^{-1}(A).

Thus every accepted observed word has an accepting lift chosen by at least one selector, and every selected accepting lift projects back to that word. Define the causal selection number

csel⁡(A,π) \operatorname{csel}(A,\pi)

as the least such mm, or infinity when no finite cover exists.

2. FPRD-T167: finite selector covers preserve stationary transport

Assume

(d,k,g,q)∈Tr⁡(A), (d,k,g,q)\in\operatorname{Tr}(A),

and let the selectors have state-set sizes s1,…,sms_1,\ldots,s_m. Then

(md,k,gm,qm∏i=1msi)∈Tr⁡(π(A)). \left(md, k, g^m, q^m\prod_{i=1}^m s_i\right) \in\operatorname{Tr}(\pi(A)).

In particular, if every selector has at most ss states, the last coordinate is at most (sq)m(sq)^m.

Proof

FPRD-T166 gives

(d,k,g,siq)∈Tr⁡(Ti−1(A)) (d,k,g,s_iq)\in\operatorname{Tr}(T_i^{-1}(A))

for every selector. FPRD-T157 combines the mm presentations by packing one node from each component into each physical node. The degrees add, the common distance remains kk, labels form an mm-fold product, and controls form the product of the siqs_iq component controls. Accept when at least one component accepts. The selector-cover equality identifies this union with π(A)\pi(A).

The construction is letter-synchronous and creates one packed node per observed letter. It does not need to enumerate all hidden histories.

3. Full tagging already has infinite raw cover number

Suppose every observed letter has h≥2h\ge 2 possible tags. At length nn, one fixed observed word has hnh^n tagged lifts. A deterministic selector chooses only one of them. Therefore no fixed finite family covers the full tagging relation at every length.

This counting fact concerns all lifts. A particular language may still have a small accepting selector cover if only a causally simple subset of its lifts is needed for acceptance.

4. FPRD-T168: the hard visible lift has infinite causal selection number

Let CC be the Kim-Park language with

C∈LIN∩PEG∖SCA. C\in\mathsf{LIN}\cap\mathsf{PEG}\setminus\mathsf{SCA}.

FPRD-T91 supplies a deterministic visibly pushdown language ACA_C whose forgotten-action projection is CC:

π(AC)=C. \pi(A_C)=C.

A deterministic visibly pushdown automaton is a finite-control, letter-synchronous one-stack machine. Each letter performs one push, keep, or pop. The persistent-stack compiler underlying FPRD-T89 and FPRD-T101 therefore gives ACA_C a degree-one, distance-two scaffolding presentation. Hence

Tr⁡(AC)≠∅. \operatorname{Tr}(A_C)\ne\varnothing.

If csel⁡(AC,π)\operatorname{csel}(A_C,\pi) were finite, FPRD-T167 would give Tr⁡(C)≠∅\operatorname{Tr}(C)\ne\varnothing, contradicting the Kim-Park theorem. Therefore

csel⁡(AC,π)=∞,Tr⁡(AC)≠∅,Tr⁡(π(AC))=∅. \operatorname{csel}(A_C,\pi)=\infty, \qquad \operatorname{Tr}(A_C)\ne\varnothing, \qquad \operatorname{Tr}(\pi(A_C))=\varnothing.

This is stronger than saying that there are exponentially many raw taggings. Even after discarding every hidden history irrelevant to acceptance, no fixed finite collection of online finite-state strategies can select all required accepting lifts.

5. Interpretation and boundary

The hard projection does not arise because one visible run needs exotic memory. The tagged language itself has one persistent stack and therefore a very small scaffold presentation. The obstruction appears when the tags are hidden and a deterministic recognizer must account for an unbounded family of incompatible online choices.

The theorem gives a necessary obstruction, not a complete characterization. Infinite causal selection number does not by itself prove that a projection is outside SCA; another presentation might recognize the projected language without selecting accepting lifts. T168 obtains the converse direction only from the independently established SCA non-membership of CC.

Finite unions, product simulations, persistent stacks, and Mealy selectors are standard constructions. FPRD-T167 records their exact transport resource composition. FPRD-T168 is a source-attributed corollary of FPRD-T91, the persistent-stack compiler, and Kim-Park Theorem 4.19. No independent proof of the Kim-Park separation or literature-priority claim is made.

Sources