PSTACK: An Optimal Online Compression Algorithm for Hysteresis-Driven Data Streams

We study online lossless compression of discrete sequences generated by hysteresis-driven processes, formalised via the Preisach operator from mathematical physics. The central object is the extremum stack Πₙ — the sequence of alternating local maxima and minima surviving the Preisach wiping-out rule. We prove three complementary results: (1) Kolmogorov minimality. The extremum stack is a minimal sufficient statistic for the class R of all computable, causal, rate-independent functionals, in the sense of Kolmogorov complexity: K (Πₙ) − O (1) ≤ KR (u₀: ₍) ≤ K (Πₙ) + O (1) No representation can answer all R-queries with strictly fewer bits. The proof uses a finite indicator family of size O (L²) over the discrete grid GL. (2) Worst-case complexity. In the output-change model, any exact R-minimal representation incurs Θ (k) output changes per step in the adversarial case — unavoidable regardless of data structure. Binary search reduces boundary detection to O (log k). A 2-3 finger tree (Hinze SCADA-like signals n/k = 1, 000×; white noise n/k = 3× (k/n → 1/3) ; adversarial signals n/k → 2× (k/n → 1/2, matching the lower bound). For sinusoidal signals at frequency f, n/k = 1/f exactly. Companion papers: Frydrych (2026a, IPL) establishes the Kolmogorov minimality result; Frydrych (2026b, IPL) establishes the worst-case complexity results. Submitted to Theoretical Computer Science (Elsevier).