Pith. sign in

REVIEW 3 minor 14 references

Fully Persistent Dynamic LCE via AVL Trees and AVL Grammars

T0 review · 0 major / 3 minor · reviewed 2026-07-03 · grok-4.3

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Path copying on AVL trees yields a fully persistent dynamic LCE structure with O(log n) worst-case update time.

desk verdict FeAVL uses AVL path copying for fully persistent dynamic LCE with clean worst-case bounds and a grammar compression result. read the letter →

arxiv 2607.01580 v1 pith:Z26U7PEY submitted 2026-07-02 cs.DS

Taiki Kaneda , Hiroki Arimura , Shunsuke Inenaga This is my paper · ORCID
classification cs.DS
keywords fullypersistentdynamicLCEAVLtreespathcopyingstringdatastructuresgrammarcompression
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The authors present FeAVL, a structure for fully persistent dynamic strings that handles equality and longest common extension queries. By applying path copying to AVL trees, it ensures that balance properties hold for every version created during updates. This resolves issues with amortized data structures like splay trees, where reuse of unbalanced versions can degrade performance. The result is split, concatenate, and character updates in O(log n) worst-case time, equality queries in O(log n) time with high probability, and LCE queries in O(log n + log squared of ell) time with high probability, while producing only O(log n) new nodes per update. They also provide a grammar-compressed version that bounds the growth of the total grammar size.

What carries the argument

Path copying over AVL trees for maintaining balanced versions of dynamic strings under persistence.

What would settle it

Finding a sequence of operations on strings where the LCE query time exceeds O(log n + log squared ell) or where more than O(log n) nodes are created per update.

Watch

Extended reading notes

Core claim

We give a fully persistent dynamic LCE structure, called FeAVL, based on path copying over AVL trees. For an operation involving string(s) of total length n, it supports split, concatenate, and single-character updates in worst-case O(log n) time, equality in worst-case O(log n) time w.h.p., and LCE in worst-case O(log n+log²ℓ) time w.h.p., where ℓ is the answer; each update creates only O(log n) new permanent nodes. We also give a grammar-compressed instantiation via AVL grammars: starting from an initial grammar of size g₀, after U updates, the total number of permanent grammar nodes is O(g₀+I+U log n_max), where I is the number of inserted fresh characters and n_max is the maximum string

Load-bearing premise

That AVL trees maintain their height balance property under path copying in all created versions without extra time overhead.

Editorial extensions

If this is right

  • Split and concatenate operations on strings of length n run in O(log n) worst-case time.
  • Single-character updates run in O(log n) worst-case time and create O(log n) new nodes.
  • Equality checks between strings run in O(log n) time with high probability.
  • LCE queries return the answer in O(log n + log²ℓ) time with high probability.
  • The AVL grammar version limits total permanent nodes to O(g0 + I + U log n_max) after U updates.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The w.h.p. bounds likely rely on randomized hashing for equality testing of tree paths.
  • This persistent structure could support versioned text editors where past states must remain accessible.
  • Similar path-copying techniques might apply to other balanced search trees for persistent string problems.
  • The grammar compression could reduce space in applications with many similar versions.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

0 major / 3 minor

Summary. The paper introduces FeAVL, a fully persistent dynamic LCE structure for strings based on path copying over AVL trees (addressing limitations of prior splay-tree approaches). For operations on strings of total length n, it claims worst-case O(log n) time for split/concatenate/single-character updates, O(log n) time w.h.p. for equality, and O(log n + log²ℓ) time w.h.p. for LCE (ℓ = answer length), with O(log n) new permanent nodes per update. It also gives an AVL-grammar compressed instantiation with total permanent nodes O(g₀ + I + U log n_max) after U updates from initial grammar size g₀.

Significance. If the analysis holds, the result supplies a fully persistent string structure with worst-case update times and explicit space overhead, extending standard AVL persistence techniques to LCE/equality queries while preserving balance across versions. The grammar-compressed variant adds a useful size bound for compressed inputs. The approach is grounded in established tree properties without ad-hoc parameters.

minor comments (3)
  1. [Abstract and §3] The w.h.p. statements for equality and LCE (abstract and §3) should explicitly state the success probability (e.g., 1-1/poly(n)) and the random source (universal hashing or sampling) to make the claims fully precise.
  2. [Abstract and §4] The grammar-compressed bound in the abstract uses n_max without prior definition; add a sentence in the introduction or §4 clarifying that n_max is the maximum length over the entire update sequence.
  3. [§2] Figure 1 (or the running example in §2) would benefit from an explicit caption noting which nodes are copied on a sample update to illustrate the O(log n) node creation claim.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of the paper and the recommendation for minor revision. No specific major comments were provided in the report.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity identified

full rationale

The derivation relies on standard path-copying persistence applied to AVL trees, whose balance invariants and O(log n) split/join/update costs are established independently of this work. The stated time bounds follow directly from those properties plus standard universal hashing for the w.h.p. equality and LCE queries; no equation or claim reduces by construction to a fitted parameter, self-citation, or renamed input. The grammar-compressed variant similarly inherits its size bound from the same tree mechanics without circular redefinition. The construction is therefore self-contained against external benchmarks.

Assumptions & free parameters 0 free parameters · 1 assumptions · 0 invented entities

No free parameters or new entities are introduced in the abstract; the work relies on standard assumptions about balanced binary search trees.

assumptions (1)
  • domain assumption AVL trees support path copying for persistence while preserving O(log n) height and balance
    This is invoked to achieve the worst-case time bounds in the FeAVL design.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Fully Persistent Dynamic LCE via AVL Trees and AVL Grammars." pith.science (2026). https://pith.science/paper/Z26U7PEY

@misc{pith2026260701580,
  author       = {Pith},
  title        = {Pith review of: Fully Persistent Dynamic LCE via AVL Trees and AVL Grammars},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/Z26U7PEY}},
  note         = {Machine review of arXiv:2607.01580}
}
abstract

We study fully persistent dynamic strings with equality and longest common extension (LCE) queries. Straightforward full persistence is problematic for the splay-based FeST structure, since the same unbalanced past version can be reused indefinitely and the usual amortized analysis no longer applies. We give a fully persistent dynamic LCE structure, called FeAVL, based on path copying over AVL trees. For an operation involving string(s) of total length $n$, it supports split, concatenate, and single-character updates in worst-case $O(\log n)$ time, equality in worst-case $O(\log n)$ time w.h.p., and LCE in worst-case $O(\log n+\log^2\ell)$ time w.h.p., where $\ell$ is the answer; each update creates only $O(\log n)$ new permanent nodes. We also give a grammar-compressed instantiation via AVL grammars: starting from an initial grammar of size $g_0$, after $U$ updates, the total number of permanent grammar nodes is $O(g_0+I+U\log n_{\max})$, where $I$ is the number of inserted fresh characters and $n_{\max}$ is the maximum string length appearing during the update sequence.

Figures

Figures reproduced from arXiv: 2607.01580 by the authors.

Figure 1
Figure 1. Dynamic operations: (a) extraction and introduction vs. the string length [PITH_FULL_IMAGE:figures/full_fig_p011_1.png] view at source ↗
Figure 2
Figure 2. Persistent operations vs. the string length [PITH_FULL_IMAGE:figures/full_fig_p012_2.png] view at source ↗
Figure 3
Figure 3. Worst case under persistence: access to the deepest element of a path [PITH_FULL_IMAGE:figures/full_fig_p012_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

14 extracted references · 14 canonical work pages

  1. [1]

    Soviet Mathematics Doklady3, 1259–1263 (1962)

    Adelson-Velsky, G.M., Landis, E.M.: An algorithm for the organization of infor- mation. Soviet Mathematics Doklady3, 1259–1263 (1962)

    work page 1962

  2. [2]

    Software: Practice and Experience25(12), 1315–1330 (1995).https://doi.org/10.1002/ spe.4380251203

    Boehm, H.J., Atkinson, R., Plass, M.: Ropes: An alternative to strings. Software: Practice and Experience25(12), 1315–1330 (1995).https://doi.org/10.1002/ spe.4380251203

    work page 1995

  3. [3]

    Journal of Computer and System Sciences38(1), 86–124 (1989).https: //doi.org/10.1016/0022-0000(89)90034-2

    Driscoll, J.R., Sarnak, N., Sleator, D.D., Tarjan, R.E.: Making data structures persistent. Journal of Computer and System Sciences38(1), 86–124 (1989).https: //doi.org/10.1016/0022-0000(89)90034-2

    work page doi:10.1016/0022-0000(89)90034-2 1989

  4. [4]

    Algorithmica85(6), 1586–1623 (2023).https://doi.org/https://doi.org/10.1007/s00453-022-01007-w

    Equi, M., Norri, T., Alanko, J., Cazaux, B., Tomescu, A.I., Mäkinen, V.: Algo- rithms and complexity on indexing founder graphs. Algorithmica85(6), 1586–1623 (2023).https://doi.org/https://doi.org/10.1007/s00453-022-01007-w

    work page doi:10.1007/s00453-022-01007-w 2023

  5. [5]

    In: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018)

    Gawrychowski, P., Karczmarz, A., Kociumaka, T., Łącki, J., Sankowski, P.: Op- timal dynamic strings. In: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018). pp. 1509–1528. SIAM (2018). https://doi.org/10.1137/1.9781611975031.99

    work page doi:10.1137/1.9781611975031.99 2018

  6. [6]

    IBM Journal of Research and Development31(2), 249–260 (1987).https://doi.org/ 10.1147/rd.312.0249

    Karp, R.M., Rabin, M.O.: Efficient randomized pattern-matching algorithms. IBM Journal of Research and Development31(2), 249–260 (1987).https://doi.org/ 10.1147/rd.312.0249

    work page doi:10.1147/rd.312.0249 1987

  7. [7]

    Bennett and Gilles Brassard

    Lipták, Z., Masillo, F., Navarro, G.: A textbook solution for dynamic strings. Theo- retical Computer Science1066, 115746 (2026).https://doi.org/10.1016/j.tcs. 2026.115746

    work page doi:10.1016/j.tcs 2026

  8. [8]

    Cambridge Uni- versity Press (2023)

    Mäkinen, V., Belazzougui, D., Cunial, F., Tomescu, A.I.: Genome-scale algorithm design: bioinformatics in the era of high-throughput sequencing. Cambridge Uni- versity Press (2023)

    work page 2023

Show all 14 references
  1. [9]

    Springer (2008).https://doi.org/https://doi.org/10.1007/ 978-3-540-77978-0_2

    Mehlhorn, K., Sanders, P.: Algorithms and data structures: The ba- sic toolbox. Springer (2008).https://doi.org/https://doi.org/10.1007/ 978-3-540-77978-0_2

    2008

  2. [10]

    Theoretical Computer Science302(1–3), 211–222 (2003).https://doi.org/10.1016/S0304-3975(02)00777-6

    Rytter, W.: Application of Lempel–Ziv factorization to the approximation of grammar-based compression. Theoretical Computer Science302(1–3), 211–222 (2003).https://doi.org/10.1016/S0304-3975(02)00777-6

    2003 doi

  3. [11]

    Sahinalp, S.C., Vishkin, U.: Data compression using locally consistent parsing. Tech. rep., UMIACS Technical Report (1995)

    1995

  4. [12]

    Journal of the ACM 32(3), 652–686 (1985).https://doi.org/10.1145/3828.3835

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

    1985 doi

  5. [13]

    Journal of the ACM (JACM)32(3), 652–686 (1985).https://doi.org/https://doi.org/10

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

    1985

  6. [14]

    Combinatorica 5(4), 367–378 (1985).https://doi.org/10.1007/BF02579253

    Tarjan, R.E.: Sequential access in splay trees takes linear time. Combinatorica 5(4), 367–378 (1985).https://doi.org/10.1007/BF02579253

    1985 doi

Pith tools

Reviewed July 3, 2026 · model on record in the stance chip above.