FPRD LabShare an approach

FPRD-T172: Acceptance-blind selection and sequential uniformization

Contents

1. The accepting-lift relation

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

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

be a letter projection. Associate to this hidden presentation the relation

RA,π={(w,w^):w^∈A, π(w^)=w}. R_{A,\pi} =\{(w,\widehat w):\widehat w\in A, \ \pi(\widehat w)=w\}.

Its domain is π(A)\pi(A). A standard synchronous sequential uniformizer is a partial finite-state transducer whose domain is exactly π(A)\pi(A) and whose output on every domain word is an accepting lift.

A causal selector in FPRD is different. It is a total projection-compatible Mealy machine on every word of Σ∗\Sigma^*. It does not have to decide whether the input belongs to π(A)\pi(A). Acceptance is checked afterward by A.

This is acceptance-blind selection: choose a hidden history online, while outsourcing recognition of successful histories to the source language.

2. Single-selector bridge

Assume the projected domain D=π(A)D=\pi(A) is regular.

Then RA,πR_{A,\pi} has a synchronous sequential uniformizer if and only if (1,s)∈Sel⁡(A,π)(1,s)\in\operatorname{Sel}(A,\pi) for some finite ss.

Selector to uniformizer

Let T be a total selector that succeeds on every word in D. Run T together with a DFA for D and accept exactly the words in D. The output remains T(w), so the resulting partial synchronous transducer has domain D and its graph is contained in RA,πR_{A,\pi}.

If T has s states and the domain DFA has r states, this construction uses at most srsr states.

Uniformizer to selector

Trim the uniformizer, add one sink state, and fill every missing transition with an arbitrary output from the appropriate projection fiber. The result is a total projection-compatible selector that agrees with the uniformizer on D. An p-state partial uniformizer therefore yields a selector with at most p+1 states.

3. FPRD-T172: the regular-source finite-family bridge

Suppose A is regular. Then a finite causal selector cover exists if and only if RA,πR_{A,\pi} contains a synchronous multi-sequential subrelation S with

dom⁡(S)=π(A). \operatorname{dom}(S)=\pi(A).

Here multi-sequential means a finite union of graphs of partial sequential functions. The subrelation need not equal all of RA,πR_{A,\pi}; it need only choose enough accepting lifts to cover the domain.

More precisely, if A has an r-state DFA and

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

then there are m partial synchronous sequential functions, each with at most sr states, whose graphs lie in RA,πR_{A,\pi} and whose domains cover π(A)\pi(A).

For selector TiT_i, its successful domain is

Di={w:Ti(w)∈A}. D_i=\{w:T_i(w)\in A\}.

Because A is regular, the product of TiT_i with the DFA for A recognizes DiD_i. Restricting TiT_i to this regular domain gives one sequential component. The selector-cover identity says ⋃iDi=π(A)\bigcup_iD_i=\pi(A).

Conversely, totalize every component of a domain-covering multi-sequential subrelation. The resulting finite selector family succeeds on every word in π(A)\pi(A).

This is a domain-covering multi-uniformization statement, not a claim that the entire accepting-lift relation is multi-sequential.

4. Strict separation on nonregular domains

The regularity hypothesis is essential. Let L be any nonregular language, set A=LA=L, and take π\pi to be the identity projection. The one-state identity Mealy machine is a causal selector:

(1,1)∈Sel⁡(L,id). (1,1)\in\operatorname{Sel}(L,\mathrm{id}).

But

RL,id={(w,w):w∈L} R_{L,\mathrm{id}}=\{(w,w):w\in L\}

has no standard sequential uniformizer. The domain of every finite sequential transducer is regular, while its required domain here is L.

Thus causal selection is strictly more permissive than standard sequential uniformization. It measures online hidden-history choice without charging the selector for recognizing the observed language.

This distinction is especially important for FPRD-T168. Its projected witness is nonregular, so failure of ordinary sequential uniformization would say little. T168 rules out the stronger possibility that even finitely many acceptance-blind online selectors can cover all accepting histories.

5. Relation to established theory

Sequential uniformization is studied as a synthesis problem: an implementation must have the same domain as the specification and choose an allowed output on that domain. Multi-sequential relations are finite unions of graphs of partial sequential functions.

The present theorem locates FPRD’s selector spectrum relative to those notions:

  • on regular source presentations, finite selection is exactly a domain-covering multi-sequential subrelation;
  • on nonregular presentations, selection remains meaningful because the selectors are acceptance-blind;
  • selector count and selector state size refine this bridge with explicit resources.

The uniformization and multi-sequential notions are established theory. FPRD’s contribution here is the acceptance-blind distinction and its connection to stationary transport. No priority claim is made for the classical transducer results.

Sources