Algorithms and complexity

Pre-query causal tracks and fixed-cut factorization

A completed computation can have a simple causal history while still requiring substantial memory before a future query is known. These results separate offline path width, online track scheduling, query-oblivious placement, and information stored in a complete snapshot at one cut.

FPRD-D30 · definition

A one-way track is placed before the query is known

Fix an integer address line and finitely many labelled persistent tracks. At each input step a track may hold its address or move one address toward smaller coordinates. A demand event $(t,p)$ is served only if a track occupies address $p$ at time $t$ . Tracks cannot teleport or be placed at a selector-chosen address after the selector is revealed.

This is a mirrored one-way multi-head automaton with a pinned coordinate convention. Calling the heads “tracks” emphasizes persistence and pre-query placement; it does not introduce a random-access memory model.

FPRD-T68 · theorem and separation

Offline width, online scheduling, and preplacement differ

For a binary word $x$ of length $T$ , let

S_T(x)=\{r:0\le r\le T,\ r\equiv T\pmod2, \ x[r:T]\text{ is an even palindrome}\}.

Appending a bit $b$ gives the exact recurrence

S_{T+1}(xb)=\{T+1\}\cup \{r-1:r\in S_T(x),\ r\ge1,\ b=x_{r-1}\}.

Along a surviving update $r\mapsto r-1$ , the virtual axis $\chi_T(r)=(T+r-1)/2$ is stationary. This explicit definition replaces an earlier compressed description in which the survivor coordinate was not recoverable from the prose alone.

Causal service orders events by

(t,p)\preceq(t',p') \quad\Longleftrightarrow\quad p'\le p\ \text{ and }\ p-p'\le t'-t.

An affine change of coordinates turns this into ordinary two-dimensional dominance. Dilworth's theorem therefore makes the minimum offline number of persistent tracks exactly the width of the event poset.

Online scheduling can be harder even at width two. Begin with $A=(28,8)$ , $B=(28,12)$ , and then $C=(36,6)$ , which can follow either earlier event. If an online scheduler puts $C$ on the $A$ -track, reveal $(38,0)$ ; otherwise reveal $(38,10)$ . Either completed poset has width two, but the scheduler needs a third track.

Now reveal $r$ selector bits only after placement and demand exactly one address

q(z)=(r+1)\operatorname{value}_2(z).

Every completed branch has one demand and hence width one, but exact pre-query service requires $2^r$ tracks. Each initial $r$ -step backward cone contains at most one target, and one holding track per target attains the bound.

FPRD-T69 · exact theorem

A fixed cut splits information between snapshots and readable cells

Fix a cut, a continuation horizon, and $k$ tracks. A complete root snapshot contains the finite control state and every labelled track position, before sensing at the cut. A layout determines a readable set $A$ , the union of its $k$ backward cones.

A cell of past inputs is $A$ -resolving if any two pasts in the cell that agree on $A$ give identical answers to every allowed continuation. Then:

The minimum number of complete snapshots in a $k$ -track factorization is the minimum number of cells in a partition of the past set such that each cell is resolving for the readable set of some layout.

A protocol induces the partition by its root snapshots; a deterministic induction proves that each resulting cell is resolving. Conversely, given a cell label and its supplied layout, a strict layered continuation stores the symbols in the readable cones and reproduces the future answers.

For late INDEX with $d=2^r$ independent data bits at sites spaced $r+1$ apart, each track reveals at most one bit. A snapshot cell can therefore contain at most $2^k$ rows, while storing the untracked bits in the snapshot attains the bound. The exact frontier is

\chi_k=2^{\max(d-k,0)}.

Limitations and hostile cases

Spacing $r+1$ is essential. With $r=2$ and sites $0,2,4,6$ , one track rooted at address two can read both zero and two. It can resolve two independent bits, so the one-bit-per-track formula does not apply.
The factorization converse starts from a supplied snapshot and layout at one cut. It is not an online prefix initializer and does not make independently optimal factorizations compatible across cuts or horizons.
Counting tracks alone is uninformative when arbitrarily many snapshots are free: zero tracks always give a finite snapshot partition. The theorem concerns the joint frontier.

Sources and evidence

Robert P. Dilworth, “A Decomposition Theorem for Partially Ordered Sets,” Annals of Mathematics 51(1), 1950, pp. 161–166 — chain-cover equality.
Arnold L. Rosenberg, “On Multi-Head Finite Automata,” IBM Journal of Research and Development 10(5), 1966, pp. 388–394 — classical multi-head context.
Andrew C. Yao and Ronald L. Rivest, “k + 1 Heads Are Better than k,” Journal of the ACM 25(2), 1978, pp. 337–340 — head-hierarchy context.
Nicole Schweikardt, “Lower Bounds for Multi-Pass Processing of Multiple Data Streams,” STACS 2009, LIPIcs 3, pp. 51–62 — streaming/head tradeoff context.
Independent finite audit output and checker source.

The model and fixed-cut theorem use classical multi-head, dominance-order, and one-way factorization ingredients. Their pinned-coordinate packaging is an FPRD formulation without a literature-priority claim. No external specialist review is recorded.