Scalar growth does not determine access

For a strictly increasing function $f:\mathbb N\to\mathbb N$ , consider

L_f=\{a^n b a^{f(n)}:n\ge0\}.

The residuals after the marker are the singleton completions $R_r=\{a^r\}$ . Put $\nu_f(r)=\min\{n:f(n)\ge r\}$ . The first prefix reaching the row $\{a^r\}$ has length

c_f(r)=\nu_f(r)+1+f(\nu_f(r))-r,

while the empty horizon- $N$ row first appears at $e_f(N)=\min\{\nu_f(N),2\}$ . Together with the pre-marker arrivals, these give

G_f(M,N)= \mathbf 1[e_f(N)\le M] +\sum_{r=0}^{N}\mathbf 1[c_f(r)\le M] +\#\{n\le M:f(n)\le N-1\}.

The largest singleton arrival controls access:

a_f(N)=\max\!\left( 1+f(0), \max_{1\le n\le\nu_f(N)} \bigl(n+f(n)-f(n-1)\bigr) \right).

Taking $f_H(0)=0$ and $f_H(1)=H\ge N$ leaves the scalar quotient history through $N$ unchanged while making $a_{f_H}(N)=H+1$ arbitrarily large.

This family is an unrestricted calibration. No finite-presentation or novelty claim is made for an arbitrary schedule.

FPRD-T50 · theorem and algorithm

Finite controllers force linear access

Fix a generalized-Dyck language and a finite total controller $M=(Q,\Omega,\delta,q_0,F)$ . For controller states $p,q$ , let $d_M(p,q)$ be the shortest length of a balanced word sending $p$ to $q$ .

If $\rho_M(s,q)$ is the shortest prefix reaching stack/controller coordinate $(s,q)$ , the final unmatched opener gives the exact recurrence

\rho_M(so,q)= \min_{p\in Q} \bigl(\rho_M(s,p)+1+d_M(\delta(p,o),q)\bigr).

Raw coordinates may merge into the same bounded language row. The correct order is therefore to minimize arrival within each semantic class and only then take the maximum over classes.

Exact access.

a_{L_M}(N)=\max_{K\in S_N} \min\{\text{arrival}(c):c\in K\}.

Let $B_M$ be the largest finite balanced distance whose source is reachable in the controller's underlying DFA. A height- $h$ legal prefix has $h+1$ balanced segments around its $h$ unmatched openers. Shortening those segments yields

a_{L_M}(N)\le\max\{1,(N+1)B_M+N\}.

For every positive horizon there is a finite controller with $B_M=2$ and access $3N+2$ , so the class-wide inequality is pointwise sharp. The witnessing controller may depend on $N$ .

FPRD-T51 · theorem

Depth thresholds have exact profiles

Let $D_{k,\ell}^{\ge r}$ contain balanced words whose stack reaches height at least $r\ge1$ , and let $D_{k,\ell}^{<r}$ be the branch that stays below it. Writing $S_k(N)=\sum_{h=0}^{N}k^h$ ,

q_{k,r}^{\ge}(N)= 1+S_k(N)+ \sum_{h=\max(0,2r-N)}^{r-1}k^h, \qquad a_{k,r}^{\ge}(N)=\max(2r,N),

q_{k,r}^{<}(N)=1+S_k(\min(N,r-1)), \qquad a_{k,r}^{<}(N)=\max(1,\min(N,r-1)).

A pre-threshold stack of height $h<r$ first becomes visible when a future of length $2r-h$ can reach the threshold and return. Post-threshold rows are distinguished by their typed closing words.

At horizon zero, every at-least-threshold language has exactly two rows, yet access equals $2r$ . Even finite presentations can therefore have a fixed row count and unbounded delay across a family.

FPRD-T52 · theorem

Remove costs created only by the controller

The linear proof does not need every reachable controller state. A balanced segment begins either at the start state or immediately after an opener in a legal Dyck prefix. Let this exact finite set of sources be $E_M$ , and let $B_M^{\mathrm{ent}}$ be its largest finite balanced distance.

Under a surjective morphism of reachable DFAs, legal-entry states map onto legal-entry states and balanced distances cannot grow. Thus ordinary DFA minimization weakly improves the certificate for one regular controller language.

More generally, two regular languages can differ away from the Dyck envelope while defining the same observed language. For a controlled-Dyck language $L\subseteq D$ , define

\beta_D(L)= \min_{\substack{R\text{ regular}\\D\cap R=L}} B_{\min(R)}^{\mathrm{ent}}.

a_L(N)\le\max\{1,(N+1)\beta_D(L)+N\}.

The minimum exists because the candidate values are a nonempty set of natural numbers. Enumerating trace-equivalent controllers approximates it from above, but the proof does not supply a general stopping test.

FPRD-T53 · theorem

Semantic observations bound every presentation

Three language-level quantities expose progressively richer behavior. The first acceptance flip $\tau_D$ sees only a changed output at an empty-stack boundary. Balanced residual access $\gamma_D$ distinguishes future behavior after balanced histories. Entry-context access $\eta_D$ repeats that experiment inside every legal unfinished stack.

\beta_D(L)\ge\eta_D(L)\ge\gamma_D(L)\ge\tau_D(L).

Although entry contexts are infinite, their relevant completion behavior is finite. In the paired exclusive-or controller, an unfinished stack is summarized by the set of endpoint pairs that some legal completion separates. Finite saturation of controller states and these summaries computes $\eta_D(L)$ exactly.

Given any controller, minimize its ordinary DFA and call its entry diameter $b_M$ . Then

\eta_D(L)\le\beta_D(L)\le b_M.

If the two computable endpoints agree, that presentation is globally optimal throughout its Dyck-trace class. The remaining difference $\sigma_D(L)=\beta_D(L)-\eta_D(L)$ is nonnegative and computable in the limit from above; equality to zero is semidecidable by endpoint coincidence.

No positive value of $\sigma_D$ is known here, and no theorem says it always vanishes.

FPRD-T54 · theorem

The modulus-three trace has zero sewing defect

In the one-bracket Dyck language, let

K_3=\{\epsilon\}\cup \{w\ne\epsilon:t(w)\equiv2\pmod3\},

where $t(w)$ is the length of the terminal run of closing brackets. A three-state controller resets on every opener and counts that final run modulo three. It is state-minimal, but its entry diameter is six.

A nested-context witness forces $\eta_D(K_3)\ge4$ . An explicit six-state trace-equivalent controller has entry diameter four, closing the sandwich:

\eta_D(K_3)=\beta_D(K_3)=4.

The sewing defect is therefore zero, but minimizing state count and minimizing entry access are different optimization problems.

FPRD-T55 · exact finite-state classification

The modulus-three frontier is exact

The natural three-state controller is state-minimal and has entry cost six. The access-optimal six-state controller from the preceding theorem has cost four. Moreover, no controller with at most five states can present the same Dyck trace at cost four. Hence the nondominated state/access pairs are exactly

(3,6)\qquad\text{and}\qquad(6,4).

The five-state exclusion is computer-assisted. The encoding is exact—it closes the balanced-word relation under concatenation and matched wrapping rather than checking words only to a cutoff—and permits unused-state padding. It relies on the trusted Z3 4.16 kernel and was independently cross-checked by CEGIS; no proof-assistant certificate is claimed.

FPRD-T56 · theorem

Modulus two has a single frontier point

For every $m\ge2$ , define

K_m=\{\epsilon\}\cup \{w\in D\setminus\{\epsilon\}:t(w)\equiv m-1\pmod m\}.

At modulus two, epsilon reaches the accepted top-level residual. The balanced word $oc$ is also accepted, while $oocc$ is the first rejected balanced factor. Thus the semantic access is four. The natural two-state controller also has entry cost four, and a one-state controller cannot define this nontrivial trace. Therefore

\eta_D(K_2)=\beta_D(K_2)=4, \qquad\text{frontier}(K_2)=\{(2,4)\}.

FPRD-T57 · exact finite-state classification

Modulus four again separates states from access

The semantic entry cost of $K_4$ is six. Its natural state-minimal controller has four states and cost eight, while an explicit six-state controller attains cost six. Exact trace comparison excludes fewer than four states, and exact finite-state search excludes cost six through five states. Consequently

\eta_D(K_4)=\beta_D(K_4)=6, \qquad \text{frontier}(K_4)=\{(4,8),(6,6)\}.

The five-state exclusion is computer-assisted. A generalized closed-relation encoding and an independently implemented one-hot CEGIS encoding both reach unsatisfiable, but both rely on the trusted Z3 kernel rather than a portable formal certificate.

FPRD-T58 · theorem and construction

The access cost is known for every modulus

Fix a legal entry context of positive stack height $h$ . A completion either uses the bare terminal descent, which distinguishes one incoming residue, or contains a later opener, which resets the terminal run and erases the incoming residue. The contextual balanced factors therefore form exactly two classes. Their first arrivals give

\eta_D(K_2)=4, \qquad \eta_D(K_m)=2(m-1)\quad(m\ge3).

A uniform controller with states $(a,b)\in\mathbb Z_m\times\{0,1\}$ records stack height modulo $m$ and whether the current terminal descent plus height has the accepting residue. Balanced factors preserve the height coordinate and realize precisely the two semantic classes. Its entry cost meets the lower bound, so

\beta_D(K_2)=4, \qquad \beta_D(K_m)=2(m-1)\quad(m\ge3).

This construction uses $2m$ states. It proves optimal access, not minimum state count at that access cost.

FPRD-T59 · theorem and construction

Even moduli admit a smaller optimal controller

When $m$ is even, the accepting terminal positions lie on one parity class. This permits a controller with an $m$ -cycle and two nonaccepting parity states. On legal prefixes it tracks the cycle position when $t+h$ is odd and the parity of the remaining height otherwise.

The resulting $(m+2)$ -state controller has trace $K_m$ and entry cost $2(m-1)$ for even $m\ge4$ , with cost four at modulus two. At modulus four it is isomorphic to the six-state witness above.

This is a constructive upper bound on state count. Minimum optimal-cost state counts remain open beyond moduli two, three, and four; no even/odd minimum-state law is asserted.

What remains open

Whether $\beta_D=\eta_D$ for every controlled-Dyck trace.
Whether $\beta_D$ has a terminating computation on useful subclasses.
How the invariant changes under a different Dyck envelope or recoding.
The minimum number of states needed to attain optimal access beyond moduli two, three, and four.
No external or specialist review of these FPRD results is recorded.

Access in controlled Dyck languages