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 Π_n — 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(Π_n) − O(1) ≤ K_R(u_{0:n}) ≤ K(Π_n) + 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 G_L. (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 & Paterson 2006) achieves O(log k) worst-case memory operations per step with exact minimality. (3) PSTACK-COMPRESS. An online algorithm maintaining Π_n in O(n) total time and O(k) space. It is asymptotically Kolmogorov-optimal: no shorter representation answers all R-queries. Experiments on synthetic signals confirm: monotone signals achieve n/k = 10,000×; 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).