Run of a deterministic table on a word
DefinitionStreamRot_Supplement_detRunp2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-informationspace-complexitystreaming-algorithms
Let be finite label sets. A deterministic table consists of an initial label and, for every time , every letter and every label , one next label . Its run on a word is the sequence of labels
This is the object produced by the same-width deterministic selection of Theorem B.4: the table lives on the same label sets as the stochastic controller, and the time is an argument of the table.
Formalization Note Label sets are , as in the published controller StreamRot.Controller, and the table entry at time (0-based) reads the letter , the page's .
Definition code
import Mathlib
namespace StreamRot
namespace Supplement
/-- The run of a deterministic table on a word: the label at cut `t ≤ N` when the initial label is `s₀` and the
label after reading the letter `a_{t+1}` at cut `t` is `next t a_{t+1} s`. Qi, Constant-Failure Width Bounds for Streaming Rotations, STOC 2027 submission (manuscript sha256 3ffd9cd7…), Theorem B.4, p.22.
**Formalization Note** Label sets are `Fin (width t)`, as in `StreamRot.Controller`, and rows are 0-based: the
table entry `next t` (`t < N`) reads the letter `w t`, the page's `a_{t+1}`. The time coordinate `t` is an
argument of the table. -/
def detRun {A : Type} {width : ℕ → ℕ} {N : ℕ} (s₀ : Fin (width 0))
(next : (t : Fin N) → A → Fin (width t) → Fin (width (t + 1))) (w : Fin N → A) :
(t : ℕ) → t ≤ N → Fin (width t)
| 0, _ => s₀
| t + 1, h => next ⟨t, h⟩ (w ⟨t, h⟩) (detRun s₀ next w t (Nat.le_of_succ_le h))
end Supplement
end StreamRot
Source
Qi, Constant-Failure Width Bounds for Streaming Rotations, STOC 2027 submission (manuscript sha256 3ffd9cd7…), Theorem B.4, p.22 (PDF 24)