pith. sign in

arxiv: 2604.12696 · v1 · submitted 2026-04-14 · 💻 cs.DS

Longest Common Extension of a Dynamic String in Parallel Constant Time

Daniel Albert This is my paper

Pith reviewed 2026-05-10 14:10 UTC · model grok-4.3

classification 💻 cs.DS
keywords longest common extensiondynamic stringsparallel algorithmsCRCW PRAMstring synchronizing setsDyck languagesquares
0
0 comments X

The pith

A parallel constant-time algorithm maintains longest common extension queries on dynamic strings using O(n^ε) work.

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

The paper presents a method to support longest common extension queries on a string that changes through insertions and deletions. It runs on a CRCW PRAM model with constant time per operation and only O(n^ε) total work for any ε greater than zero. The approach builds and maintains a hierarchy of string synchronizing sets that detect equal substrings, even when some stored data lags behind the current string by up to log n log* n updates. Queries combine the slightly stale hierarchy with a short list of recent changes to compute the correct LCE length. This is useful because LCE serves as a basic primitive for many string algorithms, and the parallel dynamic version could support efficient processing of evolving data across multiple processors.

Core claim

The algorithm maintains a string synchronizing sets hierarchy to answer substring equality queries, which are then used to answer LCE queries. To achieve constant runtime, it allows parts of its information to become outdated by up to log n log* n updates and answers queries by combining this slightly outdated information with a list of the recent changes, all while keeping total work O(n^ε) on a common CRCW PRAM.

What carries the argument

string synchronizing sets hierarchy, which answers substring equality queries used to compute LCE lengths

Load-bearing premise

String synchronizing sets can be maintained dynamically in parallel such that information outdated by up to log n log* n updates can still be combined correctly with recent changes without increasing the asymptotic work or time bounds.

What would settle it

A sequence of updates and queries on a dynamic string where the combination of outdated synchronizing sets and recent changes produces an incorrect LCE length or exceeds O(n^ε) total work.

read the original abstract

A longest common extension (LCE) query on a string computes the length of the longest common suffix or prefix at two given positions. A dynamic LCE algorithm maintains a data structure that allows efficient LCE queries on a string that can change via character insertions and deletions. A dynamic parallel constant-time algorithm is presented that can maintain LCE queries on a common CRCW PRAM with $\mathcal{O}(n^{\epsilon})$ work, for any $\epsilon > 0$. The algorithm maintains a string synchronizing sets hierarchy, which it uses to answer substring equality queries, which it in turn uses to answer LCE queries. To achieve constant runtime, the algorithm allows parts of its information to become outdated by up to $\log n \log^* n$ updates. It answers queries by combining this slightly outdated information with a list of the recent changes. Two applications of this dynamic LCE algorithm are shown. Firstly, a dynamic parallel constant-time algorithm can maintain membership in a Dyck language $D_k, k > 0$ with $\mathcal{O}(n^{\epsilon})$ work for any $\epsilon > 0$. Secondly, a dynamic parallel constant-time algorithm can maintain squares with $\mathcal{O}(n^{\epsilon})$ work for any $\epsilon > 0$.

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 paper presents a dynamic parallel algorithm for longest common extension (LCE) queries on a string subject to character insertions and deletions. It achieves constant-time operations on a common CRCW PRAM with O(n^ε) work for any ε > 0 by maintaining a hierarchy of string synchronizing sets to support substring equality queries, which are then used to answer LCE queries. To enable constant runtime, the structure tolerates information becoming outdated by up to log n log* n updates and answers queries by combining this with a list of recent changes. Applications to dynamic maintenance of membership in the Dyck language D_k and to maintaining squares are also given, both with the same time and work bounds.

Significance. If the construction and analysis hold, the result would be a notable advance in parallel dynamic string algorithms. Constant-time parallel updates/queries with sub-polynomial work is a strong guarantee that is uncommon in the literature; the tolerance for a limited amount of outdated information is a technically interesting device for avoiding full synchronization costs. The applications to Dyck-word membership and square detection illustrate that the primitive is useful beyond LCE itself.

major comments (2)
  1. [Algorithm description and query procedure] The central correctness claim rests on the dynamic maintenance of the string synchronizing sets hierarchy and the procedure that combines information outdated by up to log n log* n updates with recent changes. The manuscript must supply a detailed, self-contained argument (with explicit work and time bounds) showing that this combination preserves the correctness of substring equality queries and therefore of LCE answers without introducing extra logarithmic factors.
  2. [Work analysis] The O(n^ε) work bound for any ε > 0 is load-bearing for the stated result. The paper needs to exhibit, in the update and rebuild analysis, how the parallel CRCW PRAM implementation of the hierarchy updates and the limited-outdated-information reconciliation stays within this bound; any hidden dependence on log n or log* n would falsify the claim.
minor comments (2)
  1. [Model and preliminaries] The abstract states 'common CRCW PRAM' without further qualification; the model section should explicitly define the concurrency assumptions (e.g., arbitrary vs. priority write) used in the constant-time claims.
  2. [Applications] The applications to Dyck languages and squares are sketched only at a high level. A short paragraph or subsection showing how an LCE oracle is invoked in each case would make the utility of the primitive clearer.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful reading, positive assessment of the potential significance, and constructive major comments. We address each point below and will revise the manuscript to strengthen the presentation of the correctness argument and work analysis.

read point-by-point responses

  1. Referee: [Algorithm description and query procedure] The central correctness claim rests on the dynamic maintenance of the string synchronizing sets hierarchy and the procedure that combines information outdated by up to log n log* n updates with recent changes. The manuscript must supply a detailed, self-contained argument (with explicit work and time bounds) showing that this combination preserves the correctness of substring equality queries and therefore of LCE answers without introducing extra logarithmic factors.

    Authors: We agree that expanding the argument would improve clarity and self-containment. In the revised manuscript we will add a dedicated subsection (in Section 4) that gives a complete, self-contained proof of the query procedure. The proof will (i) formally define the state of the hierarchy after at most k = O(log n log* n) updates, (ii) describe the constant-time parallel reconciliation step that cross-checks the outdated synchronizing-set information against the maintained list of recent changes (using CRCW primitives such as constant-time hashing and parallel prefix operations), and (iii) show that any mismatch caused by outdated data is detected and corrected, thereby preserving exact substring-equality answers and hence correct LCE lengths. Explicit time and work bounds will be stated, confirming that the reconciliation introduces neither extra logarithmic factors in time nor additional work beyond the O(n^ε) envelope already established for the hierarchy. revision: yes

  2. Referee: [Work analysis] The O(n^ε) work bound for any ε > 0 is load-bearing for the stated result. The paper needs to exhibit, in the update and rebuild analysis, how the parallel CRCW PRAM implementation of the hierarchy updates and the limited-outdated-information reconciliation stays within this bound; any hidden dependence on log n or log* n would falsify the claim.

    Authors: We acknowledge the need for a fully transparent work accounting. The existing analysis already relies on the fact that each level of the synchronizing-set hierarchy can be rebuilt in O(n^ε) work for arbitrary ε > 0, with a constant number of levels. The reconciliation step processes the O(log n log* n) recent changes via a constant number of parallel CRCW operations (direct-access structures and constant-time parallel selection) whose total work is absorbed into the same O(n^ε) term; no sequential scan or log n factor is incurred. In the revision we will insert a lemma-by-lemma work breakdown immediately after the update procedure, explicitly summing the costs of hierarchy maintenance, recent-change list updates, and reconciliation, thereby demonstrating that the overall per-update work remains O(n^ε) with no hidden logarithmic dependence on n. revision: yes

Circularity Check

0 steps flagged

No significant circularity

full rationale

The derivation maintains a string synchronizing sets hierarchy as an independent building block to support substring equality queries, which are then used to answer LCE queries via a combination of slightly outdated information and recent updates. No step reduces a claimed result to a fitted parameter, self-definition, or self-citation chain; the synchronizing sets and their dynamic maintenance are presented as external primitives whose properties are invoked rather than derived from the LCE output itself. The constant-time parallel bounds and applications to Dyck languages and squares follow from this structure without internal redefinition or renaming of known results as new derivations.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the dynamic parallel maintainability of string synchronizing sets and the correctness of combining limited outdated information with recent updates. No free parameters or invented entities are identifiable from the abstract.

axioms (1)
  • domain assumption String synchronizing sets hierarchy can be maintained under insertions and deletions in the CRCW PRAM model
    Invoked to support substring equality queries that underpin LCE answers.

pith-pipeline@v0.9.0 · 5514 in / 1223 out tokens · 48692 ms · 2026-05-10T14:10:35.723331+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

24 extracted references · 24 canonical work pages

  1. [1]

    Repetition Detection in a Dynamic String

    Amihood Amir, Itai Boneh, Panagiotis Charalampopoulos, and Eitan Kondratovsky. Repetition Detection in a Dynamic String . ESA 2019 , 144:5:1--5:18, 2019. URL: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.5, https://doi.org/10.4230/LIPICS.ESA.2019.5 doi:10.4230/LIPICS.ESA.2019.5

    work page doi:10.4230/lipics.esa.2019.5 2019

  2. [2]

    An optimal O(log log N) -time parallel algorithm for detecting all squares in a string

    Alberto Apostolico and Dany Breslauer. An Optimal \ O ( log log N )\ - Time Parallel Algorithm for Detecting all Squares in a String . SIAM Journal on Computing , 25(6):1318--1331, December 1996. https://doi.org/10.1137/S0097539793260404 doi:10.1137/S0097539793260404

    work page doi:10.1137/s0097539793260404 1996

  3. [3]

    Reachability Is in DynFO

    Samir Datta, Raghav Kulkarni, Anish Mukherjee, Thomas Schwentick, and Thomas Zeume. Reachability Is in DynFO . J. ACM , 65(5):33:1--33:24, August 2018. https://doi.org/10.1145/3212685 doi:10.1145/3212685

    work page doi:10.1145/3212685 2018

  4. [4]

    A Strategy for Dynamic Programs : Start over and Muddle through

    Samir Datta, Anish Mukherjee, Thomas Schwentick, Nils Vortmeier, and Thomas Zeume. A Strategy for Dynamic Programs : Start over and Muddle through. Logical Methods in Computer Science , Volume 15, Issue 2, May 2019. https://doi.org/10.23638/LMCS-15(2:12)2019 doi:10.23638/LMCS-15(2:12)2019

    work page doi:10.23638/lmcs-15(2:12)2019 2019

  5. [5]

    Muthukrishnan

    Martin Farach-Colton , Paolo Ferragina, and S. Muthukrishnan. On the sorting-complexity of suffix tree construction. J. ACM , 47(6):987--1011, November 2000. https://doi.org/10.1145/355541.355547 doi:10.1145/355541.355547

    work page doi:10.1145/355541.355547 2000

  6. [6]

    Fich, Prabhakar L

    Faith E. Fich, Prabhakar L. Ragde, and Avi Wigderson. Relations between concurrent-write models of parallel computation. In Proceedings of the Third Annual ACM Symposium on Principles of Distributed Computing , PODC '84, pages 179--189. Association for Computing Machinery, 1984. URL: https://dl.acm.org/doi/10.1145/800222.806745, https://doi.org/10.1145/80...

    work page doi:10.1145/800222.806745 1984

  7. [7]

    Nadav Borenstein, Anej Svete, Robin Chan, Josef Valvoda, Franz Nowak, Isabelle Augenstein, Eleanor Chodroff, and Ryan Cotterell

    Merrick Furst, James B. Saxe, and Michael Sipser. Parity, circuits, and the polynomial-time hierarchy. Mathematical systems theory , 17(1):13--27, December 1984. https://doi.org/10.1007/BF01744431 doi:10.1007/BF01744431

    work page doi:10.1007/bf01744431 1984

  8. [8]

    Optimal dynamic strings

    Pawe Gawrychowski, Adam Karczmarz, Tomasz Kociumaka, Jakub a cki, and Piotr Sankowski. Optimal Dynamic Strings . In Proceedings of the 2018 Annual ACM-SIAM Symposium on Discrete Algorithms ( SODA ) , Proceedings, pages 1509--1528. Society for Industrial and Applied Mathematics , January 2018. https://doi.org/10.1137/1.9781611975031.99 doi:10.1137/1.978161...

    work page doi:10.1137/1.9781611975031.99 2018

  9. [9]

    Optimal deterministic approximate parallel prefix sums and their applications

    T. Goldberg and U. Zwick. Optimal deterministic approximate parallel prefix sums and their applications. In Proceedings Third Israel Symposium on the Theory of Computing and Systems , pages 220--228, 1995. URL: https://ieeexplore.ieee.org/abstract/document/377028, https://doi.org/10.1109/ISTCS.1995.377028 doi:10.1109/ISTCS.1995.377028

    work page doi:10.1109/istcs.1995.377028 1995

  10. [10]

    An efficient algorithm for dynamic text indexing

    Ming Gu, Martin Farach, and Richard Beigel. An efficient algorithm for dynamic text indexing. In Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms , SODA '94, pages 697--704, USA, January 1994. Society for Industrial and Applied Mathematics

    work page 1994

  11. [11]

    Descriptive complexity

    Neil Immerman. Descriptive complexity . Springer, New York u.a., 1999

    work page 1999

  12. [12]

    Simple Linear Work Suffix Array Construction

    Juha K \"a rkk \"a inen and Peter Sanders. Simple Linear Work Suffix Array Construction . In Jos C. M. Baeten, Jan Karel Lenstra, Joachim Parrow, and Gerhard J. Woeginger, editors, Automata, Languages and Programming , pages 943--955, Berlin, Heidelberg, 2003. Springer. https://doi.org/10.1007/3-540-45061-0_73 doi:10.1007/3-540-45061-0_73

    work page doi:10.1007/3-540-45061-0_73 2003

  13. [13]

    Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing , pages =

    Dominik Kempa and Tomasz Kociumaka. String synchronizing sets: Sublinear-time BWT construction and optimal LCE data structure. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing , STOC 2019, pages 756--767. Association for Computing Machinery, 2019. URL: https://dl.acm.org/doi/10.1145/3313276.3316368, https://doi.org/10.1145/331...

    work page doi:10.1145/3313276.3316368 2019

  14. [14]

    Liu and Richard Peng and Aaron Sidford , editor =

    Dominik Kempa and Tomasz Kociumaka. Dynamic Suffix Array with Polylogarithmic Queries and Updates . In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing , pages 1657--1670, June 2022. https://arxiv.org/abs/2201.01285 arXiv:2201.01285 , https://doi.org/10.1145/3519935.3520061 doi:10.1145/3519935.3520061

    work page doi:10.1145/3519935.3520061 2022

  15. [15]

    Internal Pattern Matching Queries in a Text and Applications

    Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, and Tomasz Wale \'n . Internal Pattern Matching Queries in a Text and Applications . SIAM Journal on Computing , 53(5):1524--1577, October 2024. https://doi.org/10.1137/23M1567618 doi:10.1137/23M1567618

    work page doi:10.1137/23m1567618 2024

  16. [16]

    Landau and Uzi Vishkin

    Gad M. Landau and Uzi Vishkin. Fast string matching with k differences. Journal of Computer and System Sciences , 37(1):63--78, August 1988. https://doi.org/10.1016/0022-0000(88)90045-1 doi:10.1016/0022-0000(88)90045-1

    work page doi:10.1016/0022-0000(88)90045-1 1988

  17. [17]

    Mehlhorn, R

    K. Mehlhorn, R. Sundar, and C. Uhrig. Maintaining dynamic sequences under equality tests in polylogarithmic time. Algorithmica , 17(2):183--198, 1997. https://doi.org/10.1007/BF02522825 doi:10.1007/BF02522825

    work page doi:10.1007/bf02522825 1997

  18. [18]

    Dyn-FO : A parallel, dynamic complexity class

    Sushant Patnaik and Neil Immerman. Dyn- FO : A Parallel , Dynamic Complexity Class . Journal of Computer and System Sciences , 55(2):199--209, 1997. URL: https://linkinghub.elsevier.com/retrieve/pii/S0022000097915208, https://doi.org/10.1006/jcss.1997.1520 doi:10.1006/jcss.1997.1520

    work page doi:10.1006/jcss.1997.1520 1997

  19. [19]

    Work-sensitive dynamic complexity of formal languages

    Jonas Schmidt, Thomas Schwentick, Till Tantau, Nils Vortmeier, and Thomas Zeume. Work-sensitive Dynamic Complexity of Formal Languages . In Stefan Kiefer and Christine Tasson, editors, Foundations of Software Science and Computation Structures , pages 490--509. Springer International Publishing, 2021. https://doi.org/10.1007/978-3-030-71995-1_25 doi:10.10...

    work page doi:10.1007/978-3-030-71995-1_25 2021

  20. [20]

    u ller, J. Stoer, N. Wirth, and Wolfgang H \

    Yossi Shiloach and Uzi Vishkin. Finding the maximum, merging and sorting in a parallel computation model. In W. Brauer, P. Brinch Hansen, D. Gries, C. Moler, G. Seegm \"u ller, J. Stoer, N. Wirth, and Wolfgang H \"a ndler, editors, Conpar 81 , pages 314--327, Berlin, Heidelberg, 1981. Springer. https://doi.org/10.1007/BFb0105127 doi:10.1007/BFb0105127

    work page doi:10.1007/bfb0105127 1981

  21. [21]

    Fast Parallel Computation of Longest Common Prefixes

    Julian Shun. Fast Parallel Computation of Longest Common Prefixes . In SC '14: Proceedings of the International Conference for High Performance Computing , Networking , Storage and Analysis , pages 387--398, November 2014. https://doi.org/10.1109/SC.2014.37 doi:10.1109/SC.2014.37

    work page doi:10.1109/sc.2014.37 2014

  22. [22]

    Simulation of Parallel Random Access Machines by Circuits

    Larry Stockmeyer and Uzi Vishkin. Simulation of Parallel Random Access Machines by Circuits . SIAM Journal on Computing , 13(2):409--422, May 1984. https://doi.org/10.1137/0213027 doi:10.1137/0213027

    work page doi:10.1137/0213027 1984

  23. [23]

    Leslie G. Valiant. Parallelism in Comparison Problems . SIAM Journal on Computing , 4(3):348--355, 1975. URL: https://epubs.siam.org/doi/abs/10.1137/0204030, https://doi.org/10.1137/0204030 doi:10.1137/0204030

    work page doi:10.1137/0204030 1975

  24. [24]

    Linear pattern matching algorithms

    Peter Weiner. Linear pattern matching algorithms. In 14th Annual Symposium on Switching and Automata Theory (Swat 1973) , pages 1--11, October 1973. https://doi.org/10.1109/SWAT.1973.13 doi:10.1109/SWAT.1973.13

    work page doi:10.1109/swat.1973.13 1973