{"id":"5d352684-c058-422f-8e7c-67750ec631b6","arxiv_id":"2607.05004","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"First compressed online algorithms for LRS and smallest suffixient sets achieve O(r log n + n) bits and O(log^{2} n / log log n) worst-case time per character, plus matching Omega(n)-bit space lower bounds.","lead":"The paper gives the first compressed-space online algorithms that maintain smallest suffixient sets and compute longest repeating suffixes, with two worst-case space-time trade-offs driven by BWT run count r. It also proves that any deterministic online LRS algorithm needs Omega(n) bits of peak space even on constant alphabets, and extends the bound to two natural SSS variants.","discovery_kind":"new_method","skeptic_critique":{"model":"grok-4.5","headline":"No significant objection identified","rationale":"The paper carefully reduces both online LRS and length-annotated rightmost SSS maintenance to a common suite of dynamic RL-BWT, sampled PA/LCS, and RMQ primitives whose space and worst-case time are analysed in Lemmas 5–10. The lower-bound reductions (Lemmas 17 and the min-RSSS argument of Theorem 19) are short and self-contained. The advance-knowledge-of-n issue is already isolated by the reader and does not invalidate the asymptotic statements. A concrete sanity check on the running example is still worthwhile, but no load-bearing flaw is visible that would move the verdict away from ACCEPT.","tokens_in":28889,"tokens_out":439,"duration_ms":3659,"concrete_test":"Independently re-derive the LCS update formulas after Lemma 4 and the φ/PLCS recovery of Proposition 2 on the running example of Figure 1 (T[1..10]=$AGCACAGCA); confirm that the inserted LCS values x,y and the recovered LCS[3]=1 match the figure, and that the same identities hold after one further character append.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claims (Theorems 11/14, Corollaries 12/15, Theorem 13) rest on standard dynamic RL-BWT maintenance (Lemma 4), reducibility of PLCS values (Proposition 2), B-tree block enumeration via φ-queries, and RMQ/NSV/PSV support (Lemmas 5–10). The only modelling caveat already flagged by the reader—advance knowledge of n to fix L and F—is stated explicitly in Section 2 and does not affect the general O(τ_i + log r_i) bounds or the Ω(n)-bit lower bound. No hidden circularity, incorrect reduction, or unproven lemma appears to undermine the strongest claim.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.5","summary":"The paper gives the first compressed-space online algorithms for constructing smallest suffixient sets and for computing the longest repeating suffix (LRS) of successive prefixes of a text T[1..n]. Using an incremental run-length BWT of the reverse text together with a B-tree over PA/LCS blocks of size L and a dynamic fusion tree over irreducible PLCS samples, it obtains two worst-case trade-offs: O(r log n + n) bits and O(log^{2} n / log log n) time per character, or O(r log n + n log log n) bits and O((log n / log log n)^{2}) time (Theorems 11, 14 and Corollaries 12, 15). It also proves an Ω(n)-bit peak-space lower bound for any deterministic online LRS algorithm over a constant alphabet (Theorem 13) and extends the bound, via short reductions, to length-annotated and rightmost smallest suffixient sets (Lemma 17, Theorem 19).","tokens_in":29104,"tokens_out":720,"duration_ms":5275,"significance":"The work closes a clear gap: previous online SSS constructions used O(n) words, while the best compressed LRS algorithm of Prezza–Rosone was amortized O(log^{2} n). The new bounds are worst-case, improve the amortized bound by Θ(log log n) or Θ((log log n)^{2}), and match the Ω(n)-bit lower bound (up to constants) when r = O(n / log n). The lower-bound reductions cleanly link LRS and SSS maintenance. The technical machinery—reducible PLCS values, fusion-tree samples at run tops, and B-tree RMQ/NSV/PSV—is carefully developed and appears reusable for other online string problems.","major_comments":[],"minor_comments":[{"comment":"Section 2 states that the concrete trade-offs assume n is known from the first round so that L and F can be fixed. A short remark on a doubling scheme (or an explicit statement that only the general O(τ_i + log r_i) bounds hold without advance knowledge of n) would make the modelling assumption fully transparent to practitioners.","section":null},{"comment":"In the proof of Proposition 2 the telescoping argument for ϕ is correct but terse; a one-sentence reminder that reducibility also implies ϕ(p+1)=ϕ(p)+1 would help readers who have not recently consulted the PLCP literature.","section":null},{"comment":"Table 1 lists previous LRS/SSS bounds; adding a column that distinguishes amortized versus worst-case time would make the improvement over Prezza–Rosone and over the suffix-tree algorithms immediately visible.","section":null},{"comment":"A few typographical inconsistencies appear (e.g., “therun top”, missing spaces after commas in some complexity expressions). A light copy-edit pass would remove them.","section":null}],"recommendation":"accept","confidential_remarks":"The manuscript is already in strong shape for a theory venue. The only modelling caveat (advance knowledge of n) is stated explicitly and does not affect the general bounds or the lower bound; I see no reason to delay acceptance for a doubling scheme. Fit for a journal specializing in algorithms and data structures is excellent."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"This paper closes a clear gap in compressed stringology: the first online algorithms that maintain smallest suffixient sets in compressed space, and the first worst-case (not amortized) compressed online LRS algorithms, together with matching Ω(n)-bit space lower bounds even for constant alphabets.\n\nWhat is new is concrete. Prior online SSS work (Fujimaru et al., Köppl–Kucherov) used explicit suffix trees and O(n) words. Prior compressed LRS (Prezza–Rosone) was amortized O(log^{2} n). Here they keep an incremental RL-BWT plus a dynamic fusion tree of irreducible PA/LCS samples and a B-tree of blocks; they recover arbitrary PA/LCS entries by φ-queries on those samples (Proposition 2 + Lemmas 5–10). The two trade-offs follow immediately: O(r log n + n) bits and O(log^{2} n / log log n) worst-case time, or O(r log n + n log log n) bits and O((log n / log log n)^{2}). For r = O(n/log n) the first bound is linear bits. The lower bound (Theorem 13) is a clean adversary argument; the two reductions to length-annotated and rightmost SSS (Lemma 17, Theorem 19) are short and correct.\n\nThe proofs track costs carefully and rest on standard primitives (Policriti–Prezza RL-BWT, Pătrașcu–Thorup fusion trees). Self-citations are to those primitives, not circular. The only modelling caveat is that the concrete L and F choices assume n is known from the first round (Section 2); without it you keep the more general O(τ_i + log r_i) bounds. That is minor and does not touch the lower bound or the general upper bounds.\n\nThis is for people who work on compressed indexes, online string algorithms, or repetitiveness measures. The math is solid, the citation pattern is appropriate, and there is no load-bearing flaw. I would send it to referees without hesitation.","headline":"First compressed online SSS plus worst-case compressed LRS with matching Ω(n)-bit lower bounds; solid, careful work with one minor modelling caveat.","tokens_in":29694,"tokens_out":563,"would_cite":true,"duration_ms":5044,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W32","68P05","68Q25"],"pacs":[],"model":"grok-4.5","headline":"Online algorithms compute longest repeating suffixes and smallest suffixient sets in compressed space with worst-case time, and any deterministic online LRS algorithm needs linear peak space.","keywords":["online algorithms","compressed data structures","run-length Burrows-Wheeler transform","longest repeating suffix","smallest suffixient sets","string repetitiveness"],"falsifier":"Implement the two trade-offs (or a fully online doubling variant) and measure peak bits and worst-case update time on a family of highly repetitive strings with known r; the measured space must stay inside O(r log n + n) (respectively O(r log n + n log log n)) while every update finishes within the claimed asymptotic bound.","tokens_in":29819,"feed_emoji":"Ὃe","tokens_out":736,"duration_ms":11097,"temperature":0.7,"pith_summary":"As a string is read character by character, two classical questions arise: what is the longest suffix of the current prefix that already appeared earlier, and what is a smallest set of positions that covers every super-maximal right extension of a right-maximal substring? The paper answers both questions with the first online algorithms that work in compressed working space measured by the number of runs r in the Burrows-Wheeler transform of the reverse text. Two concrete trade-offs are obtained: roughly O(r log n + n) bits and O(log^{2} n / log log n) worst-case time per character, or O(r log n + n log log n) bits and O((log n / log log n)^{2}) time. For highly repetitive strings the first bound collapses to linear bits. The same machinery also proves a matching lower bound: every deterministic online algorithm for the longest-repeating-suffix problem needs Ω(n) bits of peak memory even on a constant alphabet, and the lower bound transfers to the two natural variants of online smallest-suffixient-set maintenance.","feed_headline":"Compressed online LRS and suffixient sets with worst-case time","feed_subtitle":"Two trade-offs beat prior amortized bounds and prove an Ω(n)-bit space lower bound.","key_machinery":"An incremental run-length BWT of the reverse text, augmented by a dynamic fusion tree that stores only the φ- and LCS-values of the run-top positions of the prefix array, together with a B-tree of Θ(L)-sized blocks that supports block enumeration, range-minimum queries and next/previous-smaller-value queries via the same samples.","core_discovery":"There exist deterministic online algorithms that, after each character of T[1..n], compute the longest repeating suffix LRS[i] and maintain a length-annotated rightmost smallest suffixient set of the reverse prefix, using either O(r log n + n) bits and O(log^{2} n / log log n) worst-case time per character or O(r log n + n log log n) bits and O((log n / log log n)^{2}) time; any deterministic online LRS algorithm requires Ω(n) bits of peak working space even over a constant alphabet.","pith_inferences":[],"forward_implications":[],"fun_headline_variants":["Compressed-space online LRS and smallest suffixient sets","First compressed online construction of smallest suffixient sets","Online LRS needs Ω(n) bits even on constant alphabets","Run-length BWT trade-offs for online LRS and suffixient sets","Worst-case online LRS via incremental run-length BWT indexes"],"cache_read_input_tokens":16512,"weakest_assumption_plain":"The concrete trade-offs fix block size and B-tree fan-out from the first round and therefore need the final length n known in advance; without that knowledge only the more general per-round bounds hold.","fun_headline_variants_meta":{"raw":{"variants":["Compressed-space online LRS and smallest suffixient sets","First compressed online construction of smallest suffixient sets","Online LRS needs Ω(n) bits even on constant alphabets","Run-length BWT trade-offs for online LRS and suffixient sets","Worst-case online LRS via incremental run-length BWT indexes"]},"model":"grok-4.5","effort":"low","cost_usd":0.004354,"raw_usage":{"total_tokens":1425,"prompt_tokens":1001,"num_sources_used":0,"completion_tokens":93,"cost_in_usd_ticks":43540000,"prompt_tokens_details":{"text_tokens":1001,"audio_tokens":0,"image_tokens":0,"cached_tokens":128},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":331,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":1001,"tokens_out":93,"duration_ms":3437,"temperature":1.0,"reasoning_tokens":331,"cache_read_input_tokens":128,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-11T10:13:46.697343+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"Implement the two trade-offs (or a fully online doubling variant) and measure peak bits and worst-case update time on a family of highly repetitive strings with known r; the measured space must stay inside O(r log n + n) (respectively O(r log n + n log log n)) while every update finishes within the claimed asymptotic bound.","supporting_citations":[],"review_version":1}