FPRD Cross-Area Probe Set 2

Five bounded experiments across automata and formal-language theory

Date: 2026-07-27
FPRD reference point: repository commit b70ff6ccb4d333c825c598bf52f054db72d24cbb

Purpose

This is a second test of whether FPRD produces mathematical leverage outside its current worked lanes. It follows the same discipline as Probe Set 1:

1. choose one small example or question;
2. formulate it in FPRD terms;
3. complete one exact calculation, separation, or obstruction;
4. compare it with the area’s established language;
5. promote, retain, or stop.

The five new areas are:

• alternating finite automata;
• streaming string transducers;
• Parikh automata and counter recognition;
• probabilistic finite automata;
• queue automata.

The report does not claim that any derived statement is new to the literature. “Derived result” means that the calculation was completed during the probe. Novelty would require a focused comparator audit.

Executive result

The second set is positive, but not because every probe opens a new research program. Two probes produce plausible extensions of FPRD, one gives a useful quantitative calibration, and two tell us where not to overinterpret finite shadows.

The strongest single finding is the Parikh formula

$$q_k(N) =1+\binom{N+k}{k}-\binom{N}{k}.$$

It counts the exact horizon-$N$ residual shadows of the language in which $k$ letter counts are equal. Its growth has degree $k-1$, exactly the number of independent counter differences.

The most important conceptual finding comes from the transducer and probabilistic probes together:

An FPRD observation budget may need more than future-input depth. Output resolution and readout margin can be independent resources.

Probe 1: Alternation as an obligation basis

Bounded question

Can FPRD distinguish a small generating basis of recognition obligations from the much larger set of exact residual configurations that the basis generates?

Setup

Let

$$\Sigma_n=\{1,\ldots,n\}$$

and define

$$\mathrm{All}_n =\{w\in\Sigma_n^*: \text{every symbol in }\Sigma_n \text{ occurs in }w\}.$$

An alternating finite automaton can recognize this language using one obligation $q_i$ for each required symbol. Its initial condition is

$$q_1\wedge\cdots\wedge q_n.$$

On reading $j$, obligation $q_j$ is discharged and every other obligation persists. An active obligation at the end rejects.

FPRD formulation

• Finite presentation: the $n$ obligation generators $q_1,\ldots,q_n$.
• Exact dynamic: Boolean combinations of the outstanding obligations.
• Semantic state after a prefix: the missing-symbol set $$M(w)=\Sigma_n\setminus\operatorname{alph}(w).$$
• Observation: acceptance after a finite continuation.
• Resource comparison: obligation-basis size versus residual-state count.
• Access resource: prefix length required to reach a residual configuration.

Derived result 1: exact residual count

The residual after a prefix $u$ is

$$u^{-1}\mathrm{All}_n =\{v:M(u)\subseteq\operatorname{alph}(v)\}.$$

Every subset $M\subseteq\Sigma_n$ is reachable: read each symbol outside $M$ once. Distinct missing sets yield distinct residuals. If, for example, $i\in M'\setminus M$, a continuation listing every member of $M$ accepts from $M$ but not from $M'$.

Therefore the exact residual dynamic has

$$2^n$$

states. In particular, the minimal DFA has $2^n$ states even though the alternating presentation has $n$ independent obligations.

Derived result 2: exact residual-access profile

Let $r_n(N)$ be the number of residuals reachable by prefixes of length at most $N$. A prefix of length $N$ can have introduced at most $N$ different symbols. Hence

$$r_n(N) =\sum_{j=0}^{\min(N,n)}\binom{n}{j}.$$

This is a useful refinement of the endpoint $2^n$. It records how the Boolean configuration space becomes accessible as input exposure increases.

What the probe adds

This example cleanly separates three quantities:

1. basis size: $n$ obligations;
2. exact configuration count: $2^n$ residuals;
3. access profile: a truncated binomial sum.

That distinction fits FPRD well. A finite presentation need not enumerate its semantic states. It can present a small set of generators whose combinations are the states.

However, this is primarily a calibration. Exponential succinctness of alternation and its Boolean-obligation interpretation are standard. The original theory established that alternating finite automata still recognize the regular languages while admitting large deterministic simulation blowups; see Chandra, Kozen, and Stockmeyer, “Alternation”.

Decision

Retain as calibration; do not open a separate alternation lane.

The useful FPRD object is the triple

$$(\text{basis dimension},\text{configuration count},\text{access profile}),$$

not a new proof of alternating-automaton succinctness.

A later bounded probe would be justified only if the same triple transfers between genuinely different models, such as alternating automata, register presentations, and monotone circuit dynamics. Stop if it merely restates known state-complexity bounds.

Probe 2: String transduction requires two observation axes

Bounded question

Does the ordinary FPRD tower of bounded future-input observations remain finite when the recognized object is a string-valued function rather than a Boolean language?

Setup

Assume $|\Sigma|\ge2$, and consider

$$f(w)=w\,w^R.$$

This is a standard regular string transformation. A copyless streaming string transducer realizes it with one control state and two string registers:

$$X:=Xa,\qquad Y:=aY$$

when the next symbol is $a$, followed by output $XY$. After reading $w$, the registers contain $X=w$ and $Y=w^R$.

Functional residuals

For a prefix $u$,

$$f(uv)=u\,v\,v^R\,u^R.$$

The longest output prefix common to all continuations $v$ is exactly $u$. For nonempty $u$, choose the first letter of $v$ to differ from the first letter of $u^R$; the empty continuation is also available. After removing the common prefix $u$, the normalized residual function is

$$f_u(v)=v\,v^R\,u^R.$$

At the empty continuation,

$$f_u(\varepsilon)=u^R.$$

Consequently, $u\ne u'$ implies $f_u\ne f_{u'}$. The function has infinitely many normalized residuals.

This is consistent with the classical derivative theory of sequential functions: finite derivative index characterizes sequential functions, while streaming string transducers can realize a larger class. A concise account of the derivative construction appears in Filiot and Reynier, “Transducers, Logic and Algebra for Functions of Finite Words”.

The FPRD separation

The same function therefore has:

• infinitely many exact functional residuals;
• a one-state finite control presentation;
• a two-register copyless coordinate realization.

The residual set is infinite because it stores an arbitrary pending suffix $u^R$. The register realization is finite because that suffix is represented by a coordinate updated uniformly.

This is not merely “infinite states, finite presentation,” which FPRD already expects. It exposes a defect in a one-parameter observation tower.

Even at future-input horizon $0$, the observations

$$f_u(\varepsilon)=u^R$$

range over all words. Bounding continuation length alone therefore does not produce a finite shadow.

Derived result: a necessary second budget

Introduce an output-observation budget $M$. For example, observe:

• the first $M$ output symbols; and
• whether the output ended before position $M$.

At future horizon $0$, this already produces

$$\sum_{i=0}^{M}|\Sigma|^i$$

possible output observations: exact words of length below $M$, and all length-$M$ prefixes for longer words.

The natural transduction shadow is therefore two-dimensional:

$$Q_{N,M},$$

where $N$ bounds continuation depth and $M$ bounds output resolution. Other finite output congruences could replace prefix truncation, but some second coordinate is unavoidable for this example.

Literature boundary

Streaming string transducers, the copyless restriction, and the realization of $w\mapsto ww^R$ are established. Alur and Černý give the two-variable construction and prove the connection with regular transductions in “Expressiveness of Streaming String Transducers”.

The possible FPRD contribution is not the transducer construction. It is a common resource language relating:

• residual-function growth;
• finite register-coordinate dimension;
• input observation depth;
• output observation resolution.

Decision

Promote.

This is a credible new FPRD direction because it requires a real extension of the observation architecture rather than a relabeling of an existing language-theoretic invariant.

The next bounded task should define $Q_{N,M}$ for deterministic string functions and compute it for three small functions: duplication, reversal with a delimiter, and $w\mapsto ww^R$. Compare the result with derivative index, register complexity, and output delay.

Stop if the two-axis profile is completely determined by one of those standard measures and yields no transfer theorem.

Probe 3: Parikh equality and counter-dimension recovery

Bounded question

Can a bounded residual-shadow profile recover the intrinsic dimension of a counter presentation?

Setup

For $k\ge2$, let

$$\Sigma_k=\{a_1,\ldots,a_k\}$$

and

$$E_k =\{w\in\Sigma_k^*: |w|_{a_1}=\cdots=|w|_{a_k}\}.$$

A Parikh automaton recognizes $E_k$ by incrementing the coordinate associated with each input letter and testing the final count vector against the linear set

$$\{t\mathbf 1:t\in\mathbb N\}.$$

Parikh automata are finite automata augmented with integer-vector increments and a final semilinear constraint. This is standard; see Cadilhac, Krebs, and McKenzie, “The Algebraic Theory of Parikh Automata”.

FPRD formulation

• Finite presentation: $k$ counting coordinates and one diagonal final constraint.
• Exact state after a prefix: its count vector $c=(c_1,\ldots,c_k)$.
• Observation: acceptance after a continuation of length at most $N$.
• Canonical residual coordinate: the deficit from the largest count.
• Question: how many distinct residual shadows remain visible at horizon $N$?

Canonical deficit coordinate

For a prefix count vector $c$, put

$$M=\max_i c_i,\qquad d(c)=M\mathbf 1-c.$$

Then $d(c)\in\mathbb N^k$ and $\min_i d_i=0$.

A continuation with Parikh vector $x$ completes the prefix to $E_k$ exactly when

$$c+x=t\mathbf 1$$

for some $t$. Equivalently,

$$x=d(c)+j\mathbf 1 \quad\text{for some }j\ge0.$$

Thus the residual depends only on $d(c)$.

Two normalized deficit vectors yield different residuals. Indeed, if

$$d+j\mathbf1=d'+j'\mathbf1,$$

then $d-d'$ is constant in every coordinate. Since both vectors have minimum $0$, the constant is $0$, so $d=d'$.

The shortest accepting continuation from $d$ has Parikh vector $d$ and length

$$\rho(d)=\sum_{i=1}^k d_i.$$

Derived theorem: exact horizon-$N$ shadow count

Under observations by continuations of length at most $N$:

• every normalized $d$ with $\rho(d)\le N$ forms its own class;
• every normalized $d$ with $\rho(d)>N$ lies in one common rejecting tail.

The first statement holds because a continuation with Parikh vector $d$ accepts from $d$, and no other normalized deficit accepts that same vector. The second holds because no residual in the tail has any accepting continuation within the observation horizon.

It remains to count nonnegative $k$-tuples with minimum $0$ and total at most $N$. The number of all nonnegative $k$-tuples with total at most $N$ is

$$\binom{N+k}{k}.$$

The tuples with every coordinate at least $1$ are counted, after subtracting $\mathbf1$, by

$$\binom{N}{k},$$

using the convention $\binom Nk=0$ for $N<k$.

Including the rejecting tail gives the exact formula

$$\boxed{ q_k(N) =1+\binom{N+k}{k}-\binom{N}{k}. }$$

For example,

$$q_2(N)=2N+2,$$

and the first values for $k=3$ are

$$2,5,11,20,32,47,\ldots$$

for $N=0,1,2,3,4,5,\ldots$.

The formula was checked by direct enumeration for $2\le k\le5$ and $0\le N\le8$.

The invariant that falls out

As $N\to\infty$,

$$q_k(N) =\frac{k}{(k-1)!}N^{k-1}+O(N^{k-2}).$$

Therefore the polynomial growth degree of the finite-shadow profile is

$$k-1.$$

That is exactly the dimension of the difference space

$$(c_2-c_1,\ldots,c_k-c_1)$$

needed to decide equality of all $k$ counts.

In this example, bounded residual observations recover the intrinsic number of independent counter differences without being told the counter presentation.

Why this is the strongest probe

The result connects three descriptions of the same recognition dynamic:

1. a semilinear final constraint;
2. an exact residual coordinate $d$;
3. a polynomial shadow-growth invariant.

The connection is not merely “Parikh automata have counters.” The exact finite-shadow count reads counter dimension from externally observable language behavior.

Decision

Promote strongly.

This is the best candidate in Probe Set 2 for a short FPRD theorem. The next bounded task is a comparator audit for Myhill–Nerode growth, commutative languages, semilinear residuals, and counter-machine state complexity.

If the formula is not already standard, generalize only one step: replace the diagonal by a rational linear subspace or a fixed system of homogeneous integer equations and test whether shadow-growth degree recovers codimension.

Stop if the generalization immediately becomes Ehrhart counting with no recognition-dynamic statement beyond the existing polyhedral theory.

Probe 4: Probabilistic cutpoints and precision demand

Bounded question

Can two probabilistic recognition dynamics have trivial Boolean residual behavior but nontrivial quantitative demand that an FPRD profile should record?

Setup

Consider a unary probabilistic finite automaton with two states:

• $q$, accepting;
• $r$, rejecting and absorbing.

Start in $q$. On each $a$,

$$q\longrightarrow \begin{cases} q & \text{with probability }1/2,\\ r & \text{with probability }1/2. \end{cases}$$

After $a^n$, the acceptance probability is

$$p(a^n)=2^{-n}.$$

Use strict cutpoint $0$. Every finite word has positive acceptance probability, so the cutpoint language is simply

$$\{a\}^*.$$

Its Boolean residual dynamic has one state.

Three different dynamics

The same presentation has three distinct semantic summaries:

1. Boolean cutpoint dynamic: one residual state;
2. exact probability dynamic: the infinite orbit $$(2^{-n},1-2^{-n});$$
3. orbit closure: the exact orbit plus the limiting distribution $$(0,1).$$

The cutpoint readout

$$\mathbf1[p>0]$$

accepts every reachable orbit point but rejects the limiting point. It is therefore discontinuous on the orbit closure.

Derived result: exact horizon margin

Define the horizon-$N$ cutpoint margin

$$\mu(N) =\min_{0\le n\le N}|p(a^n)-0|.$$

Then

$$\mu(N)=2^{-N}.$$

Equivalently, define a precision-demand exponent

$$h(N) =\left\lceil-\log_2\mu(N)\right\rceil.$$

For this automaton,

$$h(N)=N.$$

Any uniform additive approximation intended to preserve the strict cutpoint decision through horizon $N$ needs error smaller than $2^{-N}$. Thus a Boolean language with one residual state can still carry a linearly increasing precision requirement in its probabilistic realization.

Literature boundary

Cutpoint isolation is a classical dividing line. A cutpoint $\lambda$ is isolated when all word probabilities remain a fixed positive distance from $\lambda$; Rabin’s theorem implies that an isolated-cutpoint probabilistic automaton recognizes a regular language. A modern primary account is Fijalkow, Gimbert, Kelmendi, and Oualhadj, “Deciding the Value 1 Problem for Probabilistic Leaktight Automata”.

The present example also emphasizes that isolation is sufficient, not necessary, for regularity: the cutpoint is non-isolated while the language is regular and trivial.

What FPRD should retain

Compactness of a completed dynamic is not enough. The readout must interact tamely with the completion. For quantitative recognition, an FPRD resource signature should be able to record at least one of:

• cutpoint margin;
• required numerical precision;
• continuity or robustness of the readout.

Otherwise a compact exact state space can conceal arbitrarily unstable finite-horizon decisions.

Decision

Promote narrowly.

Do not begin a general weighted-automata program from this example. Add a small “readout stability” probe family and determine whether margin demand interacts with the existing observation tower and resource field.

Stop if the resulting definitions merely rename isolated cutpoints and standard numerical conditioning without producing a theorem that connects them to FPRD sewing or resource escape.

Probe 5: Queue automata as a finite-shadow guardrail

Bounded question

Does finite presentation plus computable finite shadows provide meaningful evidence of global tractability?

Setup

A queue automaton has finite control and a finite queue alphabet, but its configurations include arbitrary queue words:

$$Q\times\Gamma^*.$$

Queue automata are computationally powerful. Standard deterministic queue automata can simulate Turing machines, and strong undecidability persists under substantial timing restrictions. A useful survey and set of results is Beier, Holzer, and Kutrib, “Diving into the Queue”.

FPRD formulation

• Finite presentation: finite control, queue alphabet, and transition rules.
• Exact dynamic: the infinite configuration graph.
• Bounded shadow: configurations reachable within at most $N$ transition steps.
• Potential sewing question: can coherent bounded computations be assembled into a globally analyzable dynamic?

Derived result: every time-bounded shadow is finite

Suppose the initial queue length is $\ell_0$, and one transition enqueues at most $c$ symbols. After at most $N$ transitions, the queue length is at most

$$\ell_0+cN.$$

Therefore the number of possible configurations in the time-$N$ shadow is bounded by

$$|Q| \sum_{\ell=0}^{\ell_0+cN}|\Gamma|^\ell.$$

The entire bounded transition graph can be generated by exhaustive expansion. Thus this model has:

• a finite rule presentation;
• a finite, exactly computable shadow at every time bound;
• compatible restriction maps between time bounds;
• an exact infinite configuration dynamic recovered from their union.

Nevertheless, the global model can simulate arbitrary computation. Emptiness, equivalence, and other global questions can be undecidable for relevant queue models.

The guardrail

This falsifies any broad inference of the following form:

Finite presentation + exact finite shadows + coherent reconstruction implies global decidability or structural tameness.

It does not.

The missing ingredient must be a stronger uniform condition: for example, effective compactness, bounded resource strata, a stabilization theorem, a well-quasi-order, or some other property that prevents unbounded computation from being hidden across the levels.

The point is not that FPRD fails on queue automata. FPRD correctly describes them. The point is that its general architecture is broad enough to describe Turing-complete systems, so additional hypotheses must do the work in any positive theorem.

Decision

Retain as a guardrail; stop as a current research lane.

This example should be kept near any future local-to-global or sewing theorem to prevent overstatement. Do not develop queue-FPRD further unless a proposed theorem needs a counterexample or a restricted queue class supplies an independently interesting tame case.

Cross-probe synthesis

1. FPRD is not confined to one type of infinite state

The first probe set found useful distinctions for branching structure, names, time, and infinite-word acceptance. This set adds four more mechanisms:

• Boolean combinations of finitely many obligations;
• unbounded output stored in finite registers;
• lattice-valued counter deficits;
• real-valued probability coordinates.

These mechanisms are mathematically different. The fact that the same presentation/dynamic/observation/resource analysis remains useful across them is evidence that FPRD is not merely a theory of one special construction.

2. “Finite shadow” is not a single universal notion

For Boolean word languages, continuation length often gives a finite observation set. The transducer example shows that this fails for unbounded outputs. The probabilistic example shows that a finite Boolean shadow can discard the numerical resolution needed to implement its readout robustly.

The resource field should therefore allow multiple observation coordinates:

$$(\text{future depth}, \text{output resolution}, \text{numerical precision}, \ldots).$$

This need not become a large new axiom system. It can begin as a typed interface: each recognition setting declares which observation resources make its bounded shadows finite and operationally meaningful.

3. Presentation dimension and semantic-state count are different invariants

Alternation gives an exponential separation:

$$n\text{ obligations} \quad\leadsto\quad 2^n\text{ residual configurations}.$$

The Parikh example gives a different relation:

$$k-1\text{ independent differences} \quad\leadsto\quad \Theta(N^{k-1})\text{ visible shadows}.$$

This suggests a useful FPRD comparison format:

No one component should be treated as the universal complexity measure.

4. Levelwise computability does not imply a tame limit

The queue example is the necessary negative control. Compatible finite levels can encode an undecidable global computation. A positive sewing theorem needs substantive uniform hypotheses; inverse-limit language by itself provides no algorithmic conclusion.

This is important for the current FPRD program because it identifies what a future theorem must say, not just what objects it must name.

Overall assessment after two probe sets

My assessment is more positive after this second set.

FPRD appears to be a genuinely useful research framework for automata and formal-language theory in the following limited but meaningful sense:

1. it repeatedly separates finite presentation from finite semantic state;
2. it makes observation resources explicit rather than treating all distinguishability as cost-free;
3. it supports exact quantitative profiles that compare different representation regimes;
4. it exposes missing hypotheses in local-to-global claims.

That is enough to justify further work.

It is not yet enough to say that FPRD has established a new general theory. Most individual ingredients have established counterparts: alternating succinctness, transducer derivatives and registers, semilinear counter constraints, cutpoint isolation, and finite configuration truncations. The scientific question is whether FPRD produces one of the following:

• an invariant not already natural in the home literature;
• a sharper theorem using the combined resource profile;
• a transfer theorem between representation regimes;
• or a reusable obstruction that applies across several models.

Probe Set 2 provides two credible places to seek that result:

1. Parikh shadow growth: test whether observation-growth degree recovers counter rank or linear-constraint codimension in a broader class.
2. Transduction shadows: test whether two-axis observation profiles relate residual complexity to register complexity in a way not captured by output delay or existing derivatives.

The probabilistic margin example is a third, narrower possibility if it connects directly to FPRD completion or sewing.

Confidence

• Exact calculations in the five examples: high.
• Usefulness of the FPRD interpretation: medium-high.
• Novelty of the promoted directions: unresolved until targeted literature review.
• Recommendation to continue with bounded probes: high.

Recommended next work package

Do not start an exhaustive formalization campaign. Run three small contracts.

Contract A: Parikh comparator and one-step generalization

1. Audit literature on residual growth of commutative and semilinear languages.
2. Verify the formula for $E_k$ independently.
3. Replace equality of all counts by one fixed homogeneous integer system $Ac=0$.
4. Ask whether shadow-growth degree recovers an algebraic rank or codimension.

Promote only if: the result yields a recognition-theoretic invariant or reconstruction statement not already supplied by standard lattice-point counting.

Contract B: Two-axis transduction shadows

1. Define one explicit finite output observation scheme.
2. Compute $Q_{N,M}$ for three elementary regular functions.
3. Compare it with sequential derivatives, copyless-register number, and output delay.

Promote only if: two functions with similar standard complexity have different FPRD profiles, or the profile bounds a standard transducer resource.

Contract C: Readout stability

1. Define margin demand for quantitative presentations.
2. Test three two-state probabilistic automata: isolated, exponentially approaching, and exactly hitting a cutpoint.
3. Determine whether the readout extends continuously to the FPRD completion.

Promote only if: margin or continuity yields a reusable theorem involving completion, sewing, or resource escape.

These contracts preserve the bounded-probe method. Each has one exact target, one comparator review, and a clear stop condition.

Bottom line

The second probe set does not show that FPRD solves broad classes of automata problems. It shows something more useful at this stage:

FPRD continues to generate precise questions and nontrivial quantitative structure across genuinely different recognition models, while its own stop rules successfully reject mere reformulations.

The Parikh and transducer probes merit another bounded round. The probabilistic probe merits a small test. Alternation should remain a calibration, and queue automata should remain a warning against conclusions that are too broad.