promoted from data/fprd-lab/causal-track/cone-factorization-comparators.md on 2026-07-28 — status: unverified

Targeted comparator map for the cone-factorization result. Headline: the causal-track doctrine is NOT new and has two names - one-way multi-head finite automata (Rosenberg 1966) and trailing heads (Lutz et al. 2026), the latter matching the cut-and-tracks picture exactly in lag coordinates. S4’s inequality shape is a published theorem (Schweikardt STACS 2009 Thm 4.3) and its configuration count dates to Yao-Rivest 1978. Cell-probe is structurally the wrong home and should be dropped from the claim surface. Records an internal inconsistency: the one-bit-per-finger slogan is spacing-dependent while S4 charges log(M+1)+1 per head. One free strengthening: the bound covers adaptive heads.

Comparator map: cone factorization and the causal-track doctrine

Status: targeted primary-source comparison, complete for the four questions asked. Labels used exactly: classical result used, direct adaptation, not yet found to be prior, candidate novel result. The word “novel” is not used.

Headline: the doctrine is not new, and it has two names. That is the most consequential finding, because it means the work sits inside an existing literature rather than beside one.

Sources are held under ~/data/fprd-lab/causal-track/sources/ with SHA-256 recorded there and are never promoted to this repository.

1. Verdicts

2. The doctrine has two names — use them

S2’s model (fixed head count, all heads present from the start, speed $\le1$, motion in one direction only) is standard up to a mirror reflection of the direction convention. S2 measures old addresses so tracks recede leftward; the standard models measure absolute position so heads advance rightward. Every counting consequence is identical.

Name 1, classical — one-way multi-head finite automaton, 1DFA(k)/1NFA(k). Introduced by Piatkowski; studied by Rosenberg, On multi-head finite automata, IBM J. Res. Dev. 10(5), 1966, 388–394. Holzer, Kutrib & Malcher, Multi-Head Finite Automata, DCFS 2009, §2, p. 95: “If the heads never move to the left, then the k-head finite automaton is said to be one-way.” No-birth is built into the definition ($k$ is fixed in the tuple, and all heads start on the first square); no-teleportation is built into $\delta$ mapping into $S\times\{-1,0,1\}^k$.

Name 2, live 2026 — trailing heads. This is the closer match, because it has an explicit leading head defining a frontier plus heads that lag — S2’s cut-and-tracks picture exactly. Cruz, Glashausser & Lutz, One Adaptive Trailing Head Can Outperform Many Oblivious Trailing Heads, arXiv:2606.00127, §3.1: “Head $h$ is the leading head, and the others are trailing heads … the leading head moves forward in every step.” In the lag coordinate $\ell_i(n)=n-\pi_i(n)$, the leading head advances by 1 and a trailing head by $r_i\in\{0,1\}$, so $\ell_i$ holds or increases by exactly one per symbol — which is S2’s “hold or move one cell left per future symbol”, verbatim, with $I_n(p)$ its reachable set. See also Huang, Li, Lutz & Lutz, Multi-Head Finite-State Dimension, arXiv:2509.22912.

Recommendation: name the model “one-way multi-head” and note the “trailing head” correspondence. Do not coin a new name.

2.1 A free strengthening, and it should be claimed

The standard literature distinguishes data-independent / oblivious heads (trajectory depends only on $t$ and $|w|$) from data-dependent ones. S2 is stronger than data-independent: the cone $I_n(p)$ is the union over all motions, so the bound covers the adaptive case at no cost. Cruz– Glashausser–Lutz’s entire point is that adaptivity is strictly more powerful than obliviousness, so a bound that survives adaptivity is the one worth having. This should be stated explicitly; it is a real strengthening and it is free.

2.2 Vocabulary to adopt, and the contrast model

• Sensing vs non-sensing heads (whether the control detects head coincidence). S2 is silent, and need not take a position: Yao–Rivest note (p. 337) that their separation holds even with coincidence detection.
• Pebble automata are the natural contrast model for the no-birth axiom, because pebbles do have birth — they are dropped and lifted. If no-birth is doing work, pebble automata show what breaks without it.

2.3 The direct one-sentence citation for the model

Added on a second pass, and it is better than the definition cited above because it is the original and it states every clause at once. Yao & Rivest 1978, §1, p. 337:

“We consider the class of languages recognized by $k$-headed one-way finite automata … a single read-only input tape with an endmarker, and $k$ one-way reading heads which begin on the first square of the input tape and independently move toward the endmarker under the finite state control.”

Every clause of S2 is in that sentence: $k$ fixed (no birth), heads begin on the first square (no birth, no initial teleportation), one-way … toward the endmarker (single direction, no reversal), one square per step. S2 is this model mirrored. The lab must not describe the head model as unnamed.

The same page settles sensing for free: Yao–Rivest assume the control cannot detect head coincidence, but note their separation “holds even if the devices are allowed to detect coincidence.”

3. The store-or-point law is a PRODUCT law — and that is the real finding

This supersedes §3’s earlier framing and is the sharpest result of the comparison.

The steer into bit-probe and systematic/index data structures was correct about where to look and wrong about what would be found. Gál & Miltersen, The Cell Probe Complexity of Succinct Data Structures (ICALP 2003; TCS 379(3), 2007), p. 4, define exactly the store-or-point model — systematic or index structures, $\varphi(x)=x\cdot\varphi^*(x)$, the raw data kept verbatim plus an index telling you where to look.

But their laws are hyperbolic, not linear. Theorem 3, p. 4: $(r+1)\,t\ \ge\ (1/800)\,n/\log n$ — redundancy × probes, where S3 has redundancy + fingers.

The mechanism for the difference is clean, and it is the thing to say:

• In every model in that literature probe locations may depend on the query. One probe is therefore worth up to $\log n$ bits, because it carries its own address — and that is exactly what bends a sum into a hyperbola.
• “Non-adaptive” there does not mean query-oblivious. Garg & Radhakrishnan, Set Membership with Non-Adaptive Bit Probes, STACS 2017, p. 38:1 — non-adaptive means the $t$ locations do not depend on earlier probe answers; they still depend on $x$. The whole bit-probe literature, adaptive and non-adaptive alike, sits on the query-dependent side.
• S3’s fingers are placed before the address exists. Each is then worth exactly one bit of Shannon information, and the law is additive.

This should be the framing of S3. The interesting object is not the capacity lemma — which is near-trivial — and not the arithmetic. It is the regime: query-oblivious probing, which the data-structure literature does not study because there it is an artificial handicap, and which at an online cut is not a handicap at all but a theorem, since the address has not arrived yet.

“The online cut forces the query-oblivious regime, and in that regime the familiar hyperbola degenerates to a line.”

That statement is checkable, defensible, and survives a reviewer who knows Gál–Miltersen cold. Labels: the systematic/index model, classical result used — as the contrast model, not the source; the additive form under query-obliviousness, not yet found to be prior.

3.1 Cell-probe as originally framed — still the wrong home

This lab (and a third-party model) both assumed cell-probe space-vs-probe tradeoffs were the nearest relative. They are not, structurally.

In the cell-probe model probes may depend on the query, so INDEX is trivial: zero redundancy, one probe. Every tradeoff in that literature — Miltersen– Nisan–Safra–Wigderson richness/round-elimination, Gál–Miltersen redundancy × probes, Pătraşcu’s LSD — measures something INDEX does not exhibit. The entire force of S3 comes from target-independence: the fingers are placed before the address is seen. That is a query-oblivious probe restriction, and it is the restriction, not the probe budget, that does the work.

Recommendation: state plainly that cell-probe does not bind, and why. Cite it as the model that fails to see the phenomenon, not as a near-miss. That is both more honest and a stronger framing.

4. An internal inconsistency to fix before anyone else finds it

The slogan “one extra finger saves exactly one bit” is an artifact of the construction, not a law.

The exchange rate is 1 bit per finger only because the data bits sit at spacing exactly $r+1$ = cone diameter + 1. In the general one-way multihead accounting a head is worth up to $\log n$ bits, because its position is part of the configuration — the standard $s\cdot(n+1)^k$ count. S4 itself uses that count, charging $\log_2(M_r+1)+1$ per head.

So the two statements in the same package use different exchange rates, and a reviewer will notice within a page. The fix is to present the rate as tunable by the spacing, with $\log_2\chi_k+k=d$ as the boundary case, rather than as a conservation law.

5. S4’s shape is published, for a different language

Strongest comparator. Schweikardt, Lower Bounds for Multi-Pass Processing of Multiple Data Streams, STACS 2009, 51–62, Theorem 4.3, p. 55 — a single linear inequality in $\lg m$ and $k\lg(\text{positions})$ whose violation is required for solvability, which immediately yields both of S4’s corollaries. Its abstract states the intent in S4’s own terms: a lower bound on memory and number of heads. The intermediate counting step (p. 57) is S4’s snapshot fiber.

The configuration count itself is older. Yao & Rivest 1978, p. 338, has $s\cdot(\text{positions})^k$ in print, attributed there to Rosenberg 1966.

What was not found: this consequence stated for an INDEX-like addressing language. The canonical separating languages in this literature are the fold/palindrome-pairing family $L_b$ (Yao–Rivest) and set disjointness (Schweikardt). Choosing INDEX gives a cleaner information story and a fixed alphabet, but it instantiates an existing technique. Label: direct adaptation.

Also cite, so it is not thrown at the lab later: Kutrib, Malcher & Wendlandt on states-and-heads trade-offs for unary multi-head automata (DLT 2012; Acta Informatica 2014).

6. Net effect on the claim surface

• The doctrine: named, classical. Adopt the standard name.
• S1: classical.
• S4’s technique and inequality shape: classical, instantiated at a new language.
• What remains unlocated is narrow: the two-sided exact packaging of the frontier — and §4 argues that packaging should itself be weakened to a spacing-dependent statement.
• Cell-probe should be removed from the claim surface rather than cited.
• One thing gets stronger, not weaker: the bound covers adaptive heads, which the oblivious literature does not.