pith. sign in

arxiv: 2606.05245 · v1 · pith:6OCHWADAnew · submitted 2026-06-03 · 💻 cs.DS · math.FA

Worst-Case Update Complexity of the Preisach Extremum Stack

Piotr Frydrych This is my paper

Pith reviewed 2026-06-28 04:05 UTC · model grok-4.3

classification 💻 cs.DS math.FA
keywords Preisach extremum stackrate-independent functionalsworst-case complexityfinger-tree data structurebinary searchR-minimalityupdate algorithmKolmogorov complexity
0
0 comments X

The pith

Finger-tree structure brings worst-case updates of the Preisach extremum stack down to O(log k) while keeping exact R-minimality.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The Preisach extremum stack serves as the minimal sufficient statistic for computable rate-independent functionals. Its standard update runs in amortized constant time but can require linear work in the stack depth k on adversarial inputs. The paper establishes a lower bound showing that any compact exact representation must change Theta(k) outputs in the worst case. Binary search on the monotone wiping property reduces boundary detection to logarithmic time, though deletion stays linear without further machinery. A finger-tree implementation completes both search and deletion in O(log k) worst-case time per step.

Core claim

Any compact exact R-minimal representation of the Preisach extremum stack incurs Theta(k) output changes per step in the worst case under a model-independent metric; the monotone ordering of the Preisach wiping property permits binary search that reduces boundary detection to O(log k) while physical deletion remains Theta(d); a finger-tree data structure achieves O(log k) worst-case time for the complete update operation on both search and deletion while preserving exact R-minimality with no approximation error.

What carries the argument

Finger-tree implementation of the Preisach extremum stack Π_n that uses the monotone ordering of the wiping property to support binary search for boundary detection and efficient deletion.

If this is right

  • Any compact exact R-minimal representation incurs Theta(k) output changes per step in the worst case.
  • Boundary detection reduces to O(log k) via binary search on the wiping property.
  • Physical deletion costs remain Theta(d) without an advanced structure.
  • Finger-tree yields O(log k) worst-case time for both search and deletion.
  • Exact R-minimality is preserved with no approximation error.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The logarithmic bound may make real-time tracking of rate-independent functionals practical in control or simulation settings.
  • Similar monotone-ordering tricks could apply to other stack-like structures that track extrema.
  • The model-independent lower bound of Theta(k) changes indicates a fundamental limit on how compact such representations can be.

Load-bearing premise

The monotone ordering of the Preisach wiping property enables binary search for boundary detection.

What would settle it

An adversarial input sequence that forces the finger-tree version to perform more than O(log k) operations on any single update step.

read the original abstract

The Preisach extremum stack $\Pi_n$ is the minimal sufficient statistic for the class $\mathcal{R}$ of computable rate-independent functionals in the Kolmogorov complexity sense [1]. Its standard update algorithm runs in amortised $O(1)$ time, but adversarial inputs can force $\Theta(k)$ operations per step (where $k$ is the current depth). We establish a three-level complexity picture: (i) any compact exact $\mathcal{R}$-minimal representation incurs $\Theta(k)$ output changes per step in the worst case (in a model-independent output-change metric); (ii) the monotone ordering of the Preisach wiping property enables binary search, reducing boundary detection to $O(log k)$, though physical deletion remains $\Theta(d)$; (iii) a finger-tree implementation achieves $O(log k)$ worst-case time per step for both search and deletion, at the cost of a more complex data structure, while maintaining exact $\mathcal{R}$-minimality with no approximation error. These results settle the worst-case complexity of the Preisach extremum stack across all three levels.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript analyzes the worst-case update complexity of the Preisach extremum stack Π_n, the minimal sufficient statistic for the class R of computable rate-independent functionals. It establishes three results: (i) any compact exact R-minimal representation requires Θ(k) output changes per update in the worst case under a model-independent output-change metric; (ii) the monotone wiping property permits binary search to reduce boundary detection to O(log k) while deletion costs Θ(d); (iii) a finger-tree data structure achieves O(log k) worst-case time for both search and deletion while preserving exact R-minimality and zero approximation error. These settle the complexity across all three levels.

Significance. If the stated bounds and constructions hold, the work supplies a complete theoretical resolution of the worst-case complexity for this canonical data structure in hysteresis and rate-independent operator theory. The finger-tree lifting is a concrete algorithmic contribution that improves on the standard amortized O(1) implementation without sacrificing exactness.

major comments (2)
  1. [Abstract] The lower-bound claim in the abstract (any compact exact representation incurs Θ(k) output changes) is load-bearing for the three-level picture, yet the output-change metric is only named, not defined or related to the Kolmogorov-complexity minimality from [1]. Without an explicit definition or reduction showing that the metric is independent of the representation chosen, it is impossible to confirm that the bound applies uniformly rather than to one particular encoding.
  2. [Abstract] The finger-tree construction is asserted to achieve O(log k) worst-case time for both search and deletion while maintaining exact R-minimality. Because the manuscript is not accompanied by the full proof or the precise finger-tree augmentation (e.g., how the wiping-order invariants are maintained under split/merge), the central algorithmic claim cannot be verified from the given outline alone.
minor comments (2)
  1. [Abstract] The abstract refers to 'physical deletion remains Θ(d)' without defining d or relating it to the stack depth k; a short clarifying sentence would help.
  2. [Abstract] Citation [1] is invoked for the definition of Π_n and R-minimality; the manuscript should state explicitly which results from [1] are used as black boxes versus which are reproved.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments. We address each major comment below and will incorporate clarifications into the revised manuscript.

read point-by-point responses

  1. Referee: [Abstract] The lower-bound claim in the abstract (any compact exact representation incurs Θ(k) output changes) is load-bearing for the three-level picture, yet the output-change metric is only named, not defined or related to the Kolmogorov-complexity minimality from [1]. Without an explicit definition or reduction showing that the metric is independent of the representation chosen, it is impossible to confirm that the bound applies uniformly rather than to one particular encoding.

    Authors: We agree that the output-change metric requires an explicit definition and a clear link to Kolmogorov minimality for the lower bound to apply uniformly. In the revision we will insert a concise definition of the model-independent output-change metric into the abstract together with a one-sentence reduction establishing its independence from any particular encoding. This change strengthens the three-level picture without altering the stated bounds. revision: yes

  2. Referee: [Abstract] The finger-tree construction is asserted to achieve O(log k) worst-case time for both search and deletion while maintaining exact R-minimality. Because the manuscript is not accompanied by the full proof or the precise finger-tree augmentation (e.g., how the wiping-order invariants are maintained under split/merge), the central algorithmic claim cannot be verified from the given outline alone.

    Authors: The full proof of the O(log k) bounds and the precise finger-tree augmentation (including invariant maintenance under split/merge) appear in Sections 3–5 of the manuscript. The abstract supplies only a high-level statement. To improve verifiability from the abstract we will add a short sentence describing the key augmentation steps and will insert an explicit pointer to the relevant theorems. This constitutes a partial revision focused on the abstract. revision: partial

Circularity Check

1 steps flagged

Minor self-citation to prior definition of minimality; complexity results derived from model properties

specific steps
  1. self citation load bearing [Abstract]
    "The Preisach extremum stack Π_n is the minimal sufficient statistic for the class R of computable rate-independent functionals in the Kolmogorov complexity sense [1]."

    The R-minimality used to frame the complexity claims originates in the cited prior work; however the new worst-case bounds themselves are obtained from the wiping property and finger-tree mechanics rather than from any reduction to the content of [1].

full rationale

The paper cites [1] solely for the definition of Π_n as the minimal sufficient statistic for R in the Kolmogorov sense. All three levels of the new complexity analysis (lower bound on output changes, binary search via wiping monotonicity, and finger-tree lifting) are derived directly from the stated properties of the wiping rule and data-structure operations, without reducing any claimed bound or prediction back to fitted values or the cited definition by construction. This is a standard, non-load-bearing reference to prior work and does not create circularity in the derivation chain.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Analysis rests on properties of the Preisach model and the definition of R-minimality from prior work; no free parameters or new entities introduced in the abstract.

axioms (1)
  • domain assumption The Preisach wiping property admits a monotone ordering that supports binary search.
    Invoked to reduce boundary detection to O(log k).

pith-pipeline@v0.9.1-grok · 5712 in / 1118 out tokens · 39212 ms · 2026-06-28T04:05:34.943441+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

9 extracted references · 6 canonical work pages

  1. [1]

    P. Frydrych, The extremum stack is a minimal sufficient statistic for rate-independent functionals: A Kolmogorov complexity characterisa- tion, Information Processing LettersUnder review. Preprint:https: //doi.org/10.5281/zenodo.20272270(2026)

    work page doi:10.5281/zenodo.20272270(2026 2026

  2. [2]

    I.D.Mayergoyz, MathematicalModelsofHysteresis, Springer, NewYork, 1991.doi:10.1007/978-1-4612-3028-1

    work page doi:10.1007/978-1-4612-3028-1 1991

  3. [3]

    Brokate, J

    M. Brokate, J. Sprekels, Hysteresis and Phase Transitions, Springer, New York, 1996.doi:10.1007/978-1-4612-4048-8

    work page doi:10.1007/978-1-4612-4048-8 1996

  4. [4]

    D. D. Sleator, R. E. Tarjan, Self-adjusting binary search trees, Journal of the ACM 32 (3) (1985) 652–686.doi:10.1145/3828.3835

    work page doi:10.1145/3828.3835 1985

  5. [5]

    G. S. Brodal, Worst-case efficient priority queues, in: Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 1996, pp. 52–58

    1996

  6. [6]

    Hinze, R

    R. Hinze, R. Paterson, Finger trees: A simple general-purpose data structure, Journal of Functional Programming 16 (2) (2006) 197–217. doi:10.1017/S0956796805005769

    work page doi:10.1017/s0956796805005769 2006

  7. [7]

    R. Hood, R. Melville, Real-time queue operations in pure LISP, In- formation Processing Letters 13 (2) (1981) 50–54.doi:10.1016/ 0020-0190(81)90030-2

    1981

  8. [8]

    Chiarot, C

    G. Chiarot, C. Silvestri, Time series compression survey, ACM Comput- ing Surveys 55 (10) (2023) 198:1–198:32.doi:10.1145/3560814

    work page doi:10.1145/3560814 2023

  9. [9]

    Frydrych, Preisach attention: A hysteretic model of sequential mem- ory, Neural NetworksUnder review

    P. Frydrych, Preisach attention: A hysteretic model of sequential mem- ory, Neural NetworksUnder review. Preprint:https://doi.org/10. 5281/zenodo.20133615(2026). 10

    2026