FPRD-T156: Residual towers and canonical transport

1. Finite-horizon quotients

Fix a language $L\subseteq\Sigma^*$ over a finite alphabet. For a prefix $p$ and horizon $h\ge0$, define its horizon response row

$$r_h(p):\Sigma^{\le h}\to\{0,1\}, \qquad r_h(p)(z)=\mathbf 1_L(pz).$$

Let

$$Q_h=\{r_h(p):p\in\Sigma^*\}.$$

Each $Q_h$ is finite. Restriction of a row from continuations of length at most $h+1$ to those of length at most $h$ gives a surjection

$$\tau_h:Q_{h+1}\twoheadrightarrow Q_h.$$

The inverse system

$$Q_0\xleftarrow{\tau_0}Q_1 \xleftarrow{\tau_1}Q_2\xleftarrow{}\cdots$$

is the residual tower of $L$.

2. Input transport consumes horizon

For $a\in\Sigma$, define

$$D_{a,h}:Q_{h+1}\to Q_h, \qquad D_{a,h}(r)(z)=r(az).$$

This is well-defined because $|az|\le h+1$ whenever $|z|\le h$, and

$$D_{a,h}(r_{h+1}(p))=r_h(pa).$$

The derivative maps commute with restriction:

$$\tau_{h-1}D_{a,h}=D_{a,h-1}\tau_h.$$

More generally, a word $u$ of length $t$ induces

$$D_{u,h}:Q_{h+t}\to Q_h, \qquad D_{u,h}(r)(z)=r(uz).$$

Thus each input symbol spends exactly one level of finite-horizon information.

3. The inverse-limit residual machine

Let

$$\widehat Q=\varprojlim_h Q_h.$$

With every $Q_h$ discrete, $\widehat Q$ is a compact, totally disconnected space. The compatible derivative maps define continuous transitions

$$\widehat D_a:\widehat Q\to\widehat Q, \qquad (\widehat D_a x)_h=D_{a,h}(x_{h+1}).$$

Every prefix has a coherent tower

$$\eta(p)=(r_0(p),r_1(p),r_2(p),\ldots).$$

The map is equivariant:

$$\eta(pa)=\widehat D_a(\eta(p)).$$

Two prefixes have the same image exactly when they have the same full right residual. Hence $\eta$ induces an injection from the Myhill–Nerode residual space into $\widehat Q$.

Its image is dense. A basic open set fixes only finitely many coordinates, so it is determined by one largest horizon $h$. The selected element of $Q_h$ is $r_h(p)$ for some prefix $p$, and $\eta(p)$ lies in that open set.

Surjectivity need not hold. On a unary alphabet, let the characteristic sequence of $L$ be

$$1\,1 0\,1 00\,1 000\,1 0000\cdots.$$

Tails beginning inside the growing zero blocks converge to the all-zero response tower, but every actual tail contains a later one. The completion can therefore add ideal residuals not realized by prefixes.

4. Exact stabilization criterion

The following are equivalent.

1. $L$ is regular.
2. The sequence $|Q_h|$ is bounded.
3. Some restriction map $\tau_h:Q_{h+1}\to Q_h$ is bijective.
4. The residual tower stabilizes from some finite level onward.

If $L$ has finitely many full residuals, every unequal pair is separated by some finite continuation. Taking the maximum of those finitely many witness lengths shows that one $Q_h$ already separates all residuals.

Conversely, suppose $\tau_h$ is bijective. Equality of horizon-h rows then equals equality of horizon-(h+1) rows. If two prefixes agree through horizon h, they agree through h+1, so after either reads a symbol their successors agree through horizon h. Horizon-h equality is therefore a finite-index right congruence saturating $L$. Myhill–Nerode gives regularity, and no later level can split the quotient.

Because every $\tau_h$ is surjective, bounded cardinality is equivalent to an eventual equality $|Q_h|=|Q_{h+1}|$, which is equivalent to bijectivity.

5. FPRD interpretation

The tower separates two questions.

• Semantic transport is canonical: input symbols act continuously on the inverse-limit residual machine.
• Physical transport is model-dependent: a finite presentation must realize those shifts using its allowed local reads, writes, pointers, and allocation.

Regular languages are exactly the case where a finite horizon already contains the whole residual machine. Persistent models seek a different kind of finite presentation when the tower never stabilizes. A scaffold lower bound must therefore obstruct every bounded-locality realization of the shift maps, not merely show that the tower has many finite levels.

Inverse limits, profinite spaces, and topological recognition are established parts of automata theory. The FPRD contribution here is the explicit finite-horizon response tower and its use as the substrate for stationary transport. No literature-priority claim is made.

6. References

• Mai Gehrke, Serge Grigorieff, and Jean-Eric Pin, A Topological Approach to Recognition, ICALP 2010, DOI: 10.1007/978-3-642-14162-1_13.
• Mai Gehrke, Serge Grigorieff, and Jean-Eric Pin, Duality and Equational Theory of Regular Languages, ICALP 2008, DOI: 10.1007/978-3-540-70583-3_21.