Synthesizing finite input clocks on two input blocks

30 September 2026. Working research note.

A finite input clock predicts stack height from the letters it reads, without seeing the stack. On words $a^n b^m$, it might count up during the first block and down during the second. Can finite control choose a clock that stays within a fixed error of every legal run of a given pushdown source?

For this two-block restriction, the answer is decidable even when neither the clock’s size nor the allowed error is supplied. The proof turns all possible input lengths and heights into finitely many arithmetic pieces, then checks whether their slopes fit one finite clock. A feasible system constructs the clock and an error bound; an infeasible one rules out every clock in the stated class.

The example below explains the obstruction: a stack can detect when it empties and reverse direction, while input-only finite control cannot remember an arbitrarily distant turning point. This limits reflected clocks, not persistent stack implementations. Extending the synthesis test beyond two input blocks remains open in this note.

1. A stack can turn around where a finite clock cannot

Consider inputs $a^n b^m$. A deterministic stack pushes on $a$, pops on $b$ until empty, and then pushes on every further $b$. Its height is $\lvert n-m\rvert$. Finite control remembers whether it is reading $a$, descending on $b$, or growing on $b$. At empty in the descending phase, the next $b$ pushes and enters the growing phase in that same step. Inputs with $a$ after $b$ are disabled. The initial stack is empty; $n=0$ enters the growing phase on the first $b$. One stack symbol suffices. Accepting exactly at empty recognizes $\{a^n b^n:n\ge0\}$.

There is exactly one height on each legal input. Nevertheless no finite input observer, emitting $-1,0,+1$ and updating its height by $H'=\max(0,H+c)$, can stay within a constant of this source on all prefixes.

Here is a direct proof. Suppose the observer has $s$ states and a uniform error bound. After any $a^n$, follow $b$ forever. The source eventually grows at one symbol per letter. The observer’s eventually periodic $b$-output must therefore have mean $+1$: any smaller mean gives a smaller asymptotic reflected growth rate. Since each output is at most $+1$, every output on that eventual cycle is $+1$. The transient has length at most $s$. At $a^n b^n$ the clock is at least $n-s$ while the source is zero, contradicting the bound as $n$ grows.

This obstruction concerns every clock in this specified reflected-clock class. The source itself has a direct persistent implementation using one immutable stack root. It is not a lower bound on persistent representations or on its language. A different presentation of $\{a^n b^n\}$ can simply stop popping at empty and reject further $b$’s, and has a matching reflected clock.

The distinction from an absolute signed sum matters: $\lvert\#a-\#b\rvert$ tracks this example exactly. Nowotka and Srba’s treatment of Caucal’s transducer clocks uses that absolute-value convention, not our reflected recurrence. Their Example 2 and Appendix B already discuss this change from descent to growth. The example is not claimed as a new phenomenon.

2. Model and theorem

$P$ is a normalized nondeterministic real-time pushdown source: finite control, finite stack alphabet, initially empty stack, finitely many initial states, and one consumed input letter with one push/pop/keep per rule. Guards inspect top or empty only. An empty pop is disabled or explicitly a no-op. There are no epsilon actions, bulk updates or other storage tests.

Restrict legal runs to words in $a^*b^*$. This restriction is implemented by a finite phase guard and includes every prefix. All runs count, not only accepting runs. Define the height relation

$$T=\{(n,m,h):\text{a legal run on }a^n b^m\text{ ends at height }h\}.$$

A clock has complete finite input control $R$, fixed initial state, outputs $c(r,x)\in\{-1,0,1\}$, $H_0=0$ and $H'=\max(0,H+c)$. The control reads input only; it cannot inspect $H$, the source stack, or a nondeterministic choice.

Theorem. For this restricted source, it is decidable whether there exist a finite clock $C$ and $B\in\mathbb N$ such that $\lvert h-H_C(a^n b^m)\rvert\le B$ for every triple in $T$. On a positive instance one can construct $C$ and a valid $B$. Neither its state count nor $B$ must be supplied. The finite slope criterion below is necessary and sufficient.

The criterion depends only on $T$. Thus two presentations having the same height relation receive the same answer. This is not invariance under language equivalence, nor a characterization of every persistent realization. If $P$ permits other words, the language compiled by this result is $L(P)\cap a^*b^*$, not all of $L(P)$.

The finite source/guard hypotheses are directly checkable. The required semilinear description is computable from P, rather than assumed as evidence that a clock already exists. No practical complexity bound is asserted.

3. Obtaining the arithmetic data

A pushdown machine can simulate $P$, enforce $a^*b^*$, then nondeterministically stop in any configuration and pop its remaining stack, emitting one fresh letter $z$ per symbol. This constructs the context-free language

$$\{a^n b^m z^h:(n,m,h)\in T\}.$$

The draining mode is an offline analysis device, not additional real-time source work. Constructive Parikh theory therefore computes $T$ as a finite union of linear sets

$$L_i=b_i+\sum_j\mathbb N v_{ij},\qquad b_i,v_{ij}\in\mathbb N^3.\tag{1}$$

Coordinates are written $(n,m,h)$. Effective Parikh semilinearity is classical; we import it, with the explicit automaton construction of Esparza, Ganty, Kiefer and Luttenberger as a primary implementation route.

Call a component $n$-unbounded if some period has positive $n$-coordinate. For each such component put

$$g_i=\gcd_j(v_{ij})_n>0,\qquad M=\operatorname{lcm}_i g_i,$$ with $M=1$ if there are no such components.

Let $N$ be one greater than the largest base $n$-coordinate of an $n$-bounded component, or $N=0$ if no such component exists. Every triple with $n\ge N$ lies in an $n$-unbounded component. For each $n<N$, compute a semilinear description of the fiber $T_n=\{(m,h):(n,m,h)\in T\}$. From (1), coefficients of positive-$n$ periods are bounded by $n$, so enumerate them; retain zero-$n$ periods. The resulting fiber bases and periods are finite and explicit.

4. The finite slope criterion

Introduce rational unknowns

$$\begin{aligned} 0&\le\alpha\le1,\\ -1&\le\beta_r\le1 &&(0\le r<M),\\ 0&\le\gamma_n\le1 &&(0\le n<N). \end{aligned}$$

For every residue $r$ and $n$-unbounded component $i$ satisfying $r\equiv(b_i)_n\pmod{g_i}$, impose the following constraints.

• If some period of $L_i$ has positive $h$-coordinate, require, for every period $v=(u,\nu,w)$ of that component,

  $$w=\alpha u+\beta_r\nu.\tag{2}$$

• If all periods have zero $h$-coordinate, require, for every period,

  $$\alpha u+\beta_r\nu\le0.\tag{3}$$

For each $n<N$ and every period $(\nu,w)$ of every fiber component, require

$$w=\gamma_n\nu.\tag{4}$$

These are finitely many rational linear equations and weak inequalities. Feasibility over the reals and over the rationals coincide, and elimination decides feasibility and returns a rational solution. The criterion is exactly feasibility of (2)-(4) with the displayed ranges. There is no enumeration of unknown observer sizes, periods or error bounds.

The period $M$ is derived from any supplied decomposition (1). Different decompositions can change its size, but not the answer proved below. $M$ and the constructed observer size are bounds, not minimum values.

5. Why every finite clock must satisfy the criterion

5.1 Reflected unary behavior

Starting at any finite observer state and reading one letter repeatedly gives an eventually periodic output sequence. Let $S_t$ be its signed sum and $\mu$ its rational cycle mean. There is $D$ such that $\lvert S_t-\mu t\rvert\le D$ for all $t$. For initial numerical height $x\ge0$, reflection has the exact formula

$$R_x(S)_t=x+S_t-\min\left(0,\min_{0\le j\le t}(x+S_j)\right).$$

If two signed-sum paths differ by at most $D$, this formula bounds the difference of their reflected paths by $2D$. The reflected linear path is $\max(0,x+\mu t)$. Consequently

$$R_x(S)_t=\max(0,x+\mu t)+O(1),\tag{5}$$

where the constant is independent of $x$ and $t$. There are finitely many observer states, so the bound can be uniform over starting states.

Applied to the $a$-orbit from height zero, (5) gives $H(a^n)=\alpha n+O(1)$, with $\alpha=\max(0,\mu_a)\in[0,1]$. The observer state after $a^n$ is eventually periodic in $n$, say with period $p$ after threshold $K$. Applying (5) on $b$ then gives rational $\beta_j\in[-1,1]$ such that, uniformly for all $n\ge K$ and $m\ge0$,

$$H(a^n b^m)=\max(0,\alpha n+\beta_{n\bmod p}m)+O(1).\tag{6}$$

For any fixed exceptional $n$, the eventual $b$-growth rate is a rational $\gamma_n=\max(0,\mu_b)\in[0,1]$; its height differs from $\gamma_n m$ by a constant.

5.2 Linear components force a common slope

Fix a linear component and a starting point whose $n$-coordinate is at least $K$. Adding $p$ times any period preserves the clock’s $n$-residue. Scaling such directions and using (6) with bounded source error shows that every nonnegative combination $d$ of the periods satisfies

$$d_h=\max(0,\alpha d_n+\beta d_m).\tag{7}$$

If all period heights are zero, the individual directions give (3). If some direction $v$ has $v_h>0$, (7) gives $\alpha v_n+\beta v_m=v_h$. Every other positive-height period satisfies the same equality. A zero-height period $u$ first gives $\alpha u_n+\beta u_m\le0$. If that value were negative, choose $k$ large enough that the linear expression on $kv+u$ is positive. Equation (7) would then equate $kv_h$ with a strictly smaller value. Therefore the value on $u$ is zero too, yielding (2) for every period. This mixed-direction step is essential: testing the generators’ clipped values separately is weaker.

For a fixed $n$ fiber the same scaling argument with its eventual $b$-growth rate gives (4), including zero-$m$ periods.

5.3 Why the source-derived period M suffices

The $n$-projection of an $n$-unbounded component is $(b_i)_n$ plus the additive monoid generated by its period $n$-coordinates. It contains every sufficiently large integer in that congruence class modulo $g_i$. To see this, divide by the gcd, choose one positive generator $d$, and choose a nonnegative generated representative of each residue modulo $d$; adding $d$ fills the tail of that residue. Such representatives exist because the generators have gcd one. This also gives an effective finite threshold.

Fix $r$ modulo $M$. All components selected for $r$ therefore have a common sufficiently large $n\equiv r\pmod M$ in their $n$-projections. Choose $n\ge K$ as well. They all encounter the same old observer state after $a^n$, and hence the same $\beta$ in (6). In each component choose a point above this $n$ and apply Section 5.2. That $\beta$ simultaneously satisfies all its required constraints for $r$. Do this for each $r$, retaining the one common $\alpha$. The finitely many $n<N$ fibers supply their $\gamma_n$. Thus a successful clock yields a feasible finite system despite its possibly unrelated period $p$ and threshold $K$.

6. Constructing a clock from a feasible system

Given a rational solution, define $\beta(n)=\gamma_n$ if $n<N$, and $\beta(n)=\beta_{n\bmod M}$ otherwise. The intended approximation is

$$F(n,m)=\max(0,\alpha n+\beta(n)m).\tag{8}$$

For an n-unbounded component and a relevant residue, (2) makes the linear expression on the period part exactly its height. Replacing its base height by $\alpha(b_i)_n+\beta_r(b_i)_m$ changes (8) by at most $(b_i)_n+(b_i)_m+(b_i)_h$, because $\max(0,t)$ is 1-Lipschitz. Under (3), height stays at the base height and the linear expression can only decrease as periods are added, giving the same safe bound. For $n<N$, (4) gives the identical base-error bound on every computed fiber component, using the base triple $(n,m,h)$. Thus

$$\lvert h-F(n,m)\rvert\le D\tag{9}$$

on all $T$, where $D$ is the maximum coordinate sum of all $n$-unbounded original bases and all computed small-fiber bases, or zero for an empty list.

On the $j$-th $a$, let the clock emit $\lfloor\alpha j\rfloor-\lfloor\alpha(j-1)\rfloor$, a periodic 0/1 sequence. Keep $n$ exactly below $N$ and thereafter $n$ modulo $\operatorname{lcm}(M,\operatorname{den}(\alpha))$. Here $\operatorname{den}$ denotes the denominator in reduced form. On the first $b$, choose $\beta(n)$ and reset a finite phase counter. On the $j$-th $b$, emit

$$\lfloor\beta(n)j\rfloor-\lfloor\beta(n)(j-1)\rfloor.$$

These outputs lie in $\{-1,0,1\}$; for a fixed $\beta$ they are all nonnegative or all nonpositive. The resulting reflected height is exactly

$$H(a^n b^m)=\max(0,\lfloor\alpha n\rfloor+\lfloor\beta(n)m\rfloor).\tag{10}$$

It differs from $F$ by less than 2. Hence $B=D+2$ is a valid integer construction bound. Complete the observer on inputs outside $a^*b^*$ with an arbitrary sink. Its control never tests $H$. With rational numbers in reduced form, a sufficient state count, including the sink, is

$$\begin{aligned} N+\operatorname{lcm}(M,\operatorname{den}(\alpha)) &+\sum_r\operatorname{den}(\beta_r)\\ &+\sum_{n<N}\operatorname{den}(\gamma_n)+1. \end{aligned}\tag{11}$$

This proves sufficiency, effective synthesis and the theorem. The arithmetic criterion already supplies a terminating negative test; the prior fixed- clock decision theorem is not needed for this proof. It may subsequently compute the least skew for the particular clock constructed, if desired.

7. Examples that distinguish the conditions

All have normalized sources. Parity and half-rate behavior use finite control. In the last example the first $a$ nondeterministically pushes or keeps; all later $a$’s push and $b$’s keep. For the exceptional fiber, a finite state records whether any $a$ has occurred. All-run height semantics, rather than acceptance pruning, is used throughout.

For the valley $\lvert n-m\rvert$, the two linear components have base zero and periods

$$\{(1,0,1),(1,1,0)\},\qquad\{(0,1,1),(1,1,0)\}.$$

Both have $g=1$. The first forces $\alpha=1,\beta=-1$; the second forces $\beta=1$ and $\alpha+\beta=0$. The finite system is infeasible. This agrees with the direct obstruction in Section 1. It excludes all finite reflected clocks, not just small clocks tested by enumeration.

8. Persistent compilation and the boundary of the result

On a positive instance, the synthesized clock and $B$ enter the existing bounded-skew compiler. For the source restricted to $a^*b^*$, it supplies a degree-two, native-distance-two scaffold with one physical node per input letter and the reviewed fixed virtual initialization, without a padding letter. It preserves same-word prefix acceptance, including $\varepsilon$. The corresponding PEG recognizes $(L(P)\cap a^*b^*)^R$.

The $2B+1$ source-symbol buffer and (11) are construction bounds, not optima. The preservation contract is fixed-controller acceptance and the decoded deterministic stack, not separate nondeterministic histories or raw graph equivalence under arbitrary scaffold contexts. This note’s offline analysis has no bounded-time guarantee.

The valley source still has a direct immutable-stack implementation: one root, one pointer field and at most one fresh logical record per letter. Clock synthesis is therefore a sufficient route to persistent memory. Preserving past stack versions does not by itself support general replay or reuse after arbitrary context changes.

9. Literature, proof status and next question

The proof combines classical effective Parikh semilinearity, unary finite- state periodicity, reflection, numerical-semigroup tails and rational linear feasibility. The additional argument here is the common-residue construction in Section 5.3: it replaces an unknown observer period by the finite period derived from source components, and yields the exact slope test and compiler consequence. Its novelty has not been established.

Primary comparisons inspected:

• Esparza, Ganty, Kiefer and Luttenberger, Parikh’s Theorem: A simple and direct automaton construction, IPL 2011, Theorem 1.1 and Section 3. Effective semilinearity is imported, not a contribution of this note. https://archive.model.in.tum.de/um/bibdb/esparza/IPL11.pdf
• Nowotka and Srba, Height-Deterministic Pushdown Automata, MFCS 2007, Definitions 2-3, Section 4.1, Appendix B Lemma 2 and Example 2. Unique height, exact synchronization, absolute signed sums and reflected clocks are distinct conditions. The periodicity argument is established. https://people.cs.aau.dk/~srba/files/NS:MFCS:07.pdf
• Filiot, Jecker, Loding and Winter, On Equivalence and Uniformisation Problems for Finite Transducers, ICALP 2016, Theorem 2 and the resynchronization results. Choosing outputs by finite input control is related to uniformization, but our source-height relation need not be a rational word relation. No direct transfer of their decision or undecidability results is made. https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.125
• Filiot, Jecker, Madnani and Sunny, Approximate Problems for Finite Transducers, ICALP 2025. The published abstract’s approximate rational/ sequential-function distinction was checked as a nearby comparison; no theorem is imported from it. Our reflected prefix-height requirement and pushdown source are not identified with its string-distance model. https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.155

For example, the graph of $\max(0,n-m)$ as a unary-output function on $a^*b^*$ is not rational: the inverse image of $\varepsilon$ is $\{a^n b^m:m\ge n\}$, which is not regular, whereas inverse images of regular languages under a rational transduction are regular. Semilinear triples alone do not make it a rational word relation. This explains why simply invoking finite-transducer synthesis would require an additional proof.

The arithmetic implementation accepts an explicit semilinear relation. It constructs (2)-(4), solves them with exact rational Fourier-Motzkin elimination, and rechecks every positive witness. For negative examples it rechecks nonnegative multipliers of the original inequalities yielding a constant contradiction. Recorded output includes the seven input relations, all constraints, solutions or negative certificates, and finite source-formula/clock comparisons through n,m=24. Those samples do not prove the infinite theorem. The full argument is a written proof, with no independent or proof-assistant verification. PDA-to-semilinear conversion and the scaffold compiler are not implemented.

The unrestricted-input clock-synthesis question remains unresolved here. The next useful test is whether the source-derived finite-period argument extends to three fixed input blocks. That extension is not automatic: later slopes may depend on both earlier residues, and reflection retains another piecewise-linear expression. A proof must bound the joint residue information from the source, rather than enumerate observers indefinitely. No pumping or recurrence theorem for PEGs or arbitrary scaffold interfaces is asserted.