FeAVL achieves fully persistent dynamic LCE with O(log n) updates and equality, O(log n + log²ℓ) LCE w.h.p., and an AVL grammar version with O(g0 + I + U log n_max) permanent nodes.
[FL93] Joel Friedman and Nathan Linial
5 Pith papers cite this work, alongside 427 external citations. Polarity classification is still indexing.
5
Pith papers citing it
427
external citations · OpenAlex
citation-role summary
background 1
citation-polarity summary
years
2026 5roles
background 1polarities
background 1representative citing papers
Credit-based amortized analysis is sound for persistent data structures when credits are stored only on thunks, and Okasaki's debit approach receives a formal operational semantics.
Subquadratic Õ(n^{2-1/48}) algorithm for shortest tours of disjoint orthogonal polygons, plus linear-time results for ortho-convex and rectangular cases.
Presents the Cascade Log, a reference-stable tiered append structure using a coalescing interval map for handles, with Θ(A) space, O(log A) point resolution, and sublinear cost on append-dominated histories where A is the fragmentation measure.
Improved space-time tradeoffs for visibility polygon queries: O(n^{2+ε}) space for O(log n + k) time, plus better bounds in other regimes using a new polygon decomposition.
citing papers explorer
-
Fully Persistent Dynamic LCE via AVL Trees and AVL Grammars
FeAVL achieves fully persistent dynamic LCE with O(log n) updates and equality, O(log n + log²ℓ) LCE w.h.p., and an AVL grammar version with O(g0 + I + U log n_max) permanent nodes.
-
Persistent Amortised Analysis, Operationally
Credit-based amortized analysis is sound for persistent data structures when credits are stored only on thunks, and Okasaki's debit approach receives a formal operational semantics.
-
Touring a Sequence of Orthogonal Polygons
Subquadratic Õ(n^{2-1/48}) algorithm for shortest tours of disjoint orthogonal polygons, plus linear-time results for ortho-convex and rectangular cases.
-
The Cascade Log: Reference-Stable Windowing over Tiered Append Sequences
Presents the Cascade Log, a reference-stable tiered append structure using a coalescing interval map for handles, with Θ(A) space, O(log A) point resolution, and sublinear cost on append-dominated histories where A is the fragmentation measure.
-
Visibility Queries in Simple Polygons
Improved space-time tradeoffs for visibility polygon queries: O(n^{2+ε}) space for O(log n + k) time, plus better bounds in other regimes using a new polygon decomposition.