Deterministic clock-free one-pass streaming algorithms and their space
DefinitionPermutationStreams_Parity_Supplement_OnePassFix . A deterministic one-pass streaming algorithm for inputs with values in consists of a finite set of states, an initial state , a transition map and an output map into an answer set . On input it computes
The transition sees only the current state and the current value; the position is not supplied, so any counter the algorithm needs is part of its state. The algorithm may depend arbitrarily on . It uses bits when ; its space is the least such , namely .
This is the model of the paper's pattern-detection results, whose space bounds are state counts (Lemma 6.3 counts states and takes the logarithm).
Formalization Note Values are Fin n (the value stands for ); the state type is a parameter S, and finiteness is imposed as [Fintype S] wherever space is measured.
import Mathlib
namespace PermutationStreams.Parity.Supplement
/-- Braverman–Zamir §1 p.1, §1.2 p.2 and §6.1 pp.13–14: a deterministic one-pass streaming
algorithm for inputs `π(0), …, π(n-1)` with values in `Fin n` (the value `v` stands for `v + 1`).
`S` is its state set, `init` the initial state, and `step s x` the next state when the current
state is `s` and the arriving value is `x`. The transition sees only the state and the current
value: no position or clock is supplied, so a counter, if needed, lives in the (charged) state.
`out` turns the final state into the answer. The algorithm may depend arbitrarily on `n`. -/
structure OnePassAlg (n : ℕ) (S α : Type) where
init : S
step : S → Fin n → S
out : S → α
/-- The state after reading `π(0), …, π(n-1)` in order from `init`. -/
def OnePassAlg.finalState {n : ℕ} {S α : Type} (A : OnePassAlg n S α)
(π : Equiv.Perm (Fin n)) : S :=
(List.finRange n).foldl (fun s i => A.step s (π i)) A.init
/-- The answer of one pass on the input permutation `π`. -/
def OnePassAlg.run {n : ℕ} {S α : Type} (A : OnePassAlg n S α) (π : Equiv.Perm (Fin n)) : α :=
A.out (A.finalState π)
/-- The algorithm uses `s` bits: it has at most `2^s` states. The space of an algorithm is the
least such `s`, i.e. `⌈log₂ |S|⌉`. -/
def OnePassAlg.UsesBits {n : ℕ} {S α : Type} [Fintype S] (_A : OnePassAlg n S α) (s : ℕ) :
Prop :=
Fintype.card S ≤ 2 ^ s
end PermutationStreams.Parity.Supplement