{"id":"cba8c3ce-820a-43a9-94c2-76c11f59942b","arxiv_id":"1908.04686","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A set of algorithms that build LCP, PLCP, and suffix tree topology from a BWT in O(n log σ) time using o(n log σ) extra bits, plus an o(n log σ)-space BWT merging algorithm.","lead":"This paper gives faster, lower-memory algorithms for building compressed suffix tree components directly from the Burrows-Wheeler transform of a text or string collection. It closes a gap by showing the LCP array, PLCP bitvector, and suffix tree topology can be built from the BWT using just o(n log σ) bits of extra space.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Section 8's BPS construction omits leaf intervals; using only right-maximal substring intervals yields a 2n-bit sequence, not the 4n-bit suffix tree topology required by Theorem 5.","rationale":"The reader's weakest_assumption correctly identifies the central soft spot: Section 8 equates 'suffix tree intervals' with the intervals of right-maximal substrings from Lemma 4, but a complete BPS topology also requires n leaf pairs. My independent check of the construction confirms that the paper never states that leaf intervals are included, and the generated BPS would be too short and would not support leaf navigation. This is the most load-bearing concern because Theorem 5's claim that the output is a compressed suffix tree with full functionality rests directly on the correctness of the BPS topology. Since the gap is localized and plausibly repairable by adding a leaf-enumeration step or by noting an existing leaf pass, the appropriate outcome remains CONDITIONAL acceptance rather than outright rejection; the reader's verdict is unchanged. I agree with the reader's assessment and find no additional independent objection that would move the verdict.","tokens_in":28689,"tokens_out":6650,"duration_ms":76505,"concrete_test":"Take T='ab#' (or another small text) and explicitly compute the SA intervals of all right-maximal substrings as Lemma 4 would enumerate. Run Section 8's counter procedure to produce the BPS bitstring S. Then build the true BPS of the suffix tree with all internal nodes and n leaves, e.g. by the standard LCP-to-BPS transformation. Check whether S equals the true BPS and whether S has length 4n-2 (or 4n) bits with n leaf pairs. If the two differ, the omitted leaf intervals are confirmed. A second check: augment the same procedure by additionally incrementing Open[i] and Close[i] for every leaf interval [i,i], rebuild S, and verify that the result matches the true BPS; this also confirms that the gap is fixable without changing the asymptotic analysis.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 8 constructs the BPS topology by incrementing Open[l] and Close[r] only for intervals returned by Lemma 4, which are explicitly 'suffix array intervals corresponding to all right maximal text's substrings'—i.e. internal suffix tree nodes. In the Sadakane-style BPS representation used by the claimed CST, every one of the n leaves must also appear as an explicit pair of parentheses; a leaf with SA interval [i,i] contributes '(' at i and ')' at i. The paper never enumerates or adds these singleton intervals. As a result, the generated sequence has about 2*(#internal nodes) <= 2n bits, whereas the full suffix tree BPS has 4n bits, and leaf-oriented operations such as locating a leaf by select on '(' cannot work. The omission is concrete: for T='ab#', Lemma 4 yields only the root interval [1,3], so the procedure outputs '()' instead of a BPS with three leaves. This is a fixable gap—add the n leaf intervals [i,i] or generate them by a leaf-enumeration pass—but as written Theorem 5 does not build the claimed compressed suffix tree.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The manuscript studies the construction of compressed suffix tree components directly from the Burrows–Wheeler transform. It proposes algorithms to enumerate LCP values and suffix-tree intervals in O(n log σ) time with o(n log σ) bits of working space, and then uses them to build the PLCP bitvector and a BPS representation of the suffix tree topology in O(n(log σ + ε^{-1} log log n)) time with ε·n log σ + o(n) bits of working space. These results are combined into Theorem 5, which claims a compressed suffix tree in n log σ + 6n + o(n log σ) bits of space. The paper also presents a BWT-merging algorithm for string collections and reports an implementation (bwt2lcp, merge) on DNA data. The central claim is that this is the first succinct-space construction of all compressed suffix tree components from the BWT.","tokens_in":28870,"tokens_out":10721,"duration_ms":105362,"significance":"If the results were fully established, the LCP and PLCP constructions would improve the state of the art by replacing O(n)-bit working-space algorithms with o(n log σ)-bit algorithms, and the BWT-merge algorithm would improve the space of earlier work by Belazzougui et al. The paper is detailed, with careful complexity accounting in Sections 5 and 7, no fitted parameters, and reproducible experimental comparisons. However, the BPS construction in Section 8 omits the n leaf intervals, so Lemma 7 and Theorem 5 do not actually produce the claimed suffix tree topology as written. This is a local but load-bearing gap; the rest of the paper appears sound and the gap is likely fixable.","major_comments":[{"comment":"The topology construction increments Open[l] and Close[r] only for intervals returned by Lemma 4, which is explicitly restricted to the suffix array intervals of right-maximal text substrings. These are the internal suffix tree nodes. In the Sadakane BPS representation used by Theorem 5, each leaf with SA interval [i,i] must also contribute an opening parenthesis at position i and a closing parenthesis at position i, but such singleton leaf intervals are not right-maximal in general and are never enumerated by Lemma 4. The resulting parenthesis sequence therefore has at most 2·(#internal nodes) ≤ 2n bits instead of the roughly 4n bits of a suffix tree BPS, and leaf-oriented operations such as locating a leaf by select on '(' cannot work. Concretely, for T='ab#', Lemma 4 returns only the root interval [1,3], so the procedure outputs the sequence '()' rather than a BPS with three leaves. This is a correctness gap in Lemma 7 and in Theorem 5; a fix requires enumerating all leaf intervals [i,i] or adding them in a separate pass before the counter phase.","section":"Section 8, Lemmas 4 and 7"},{"comment":"The proof of Theorem 5 states that augmenting the BWT into a CSA can be done in O(n log σ) time and n + o(n) bits of working space. This is not reconciled with Theorem 5's stated working-space bound of ε·n log σ + o(n) bits on top of input and output: for σ = O(1) and small ε, n + o(n) exceeds the allowed amount. If the n-bit structures for suffix array sampling are intended to be placed in the output space (as is done in Lemma 1), that reuse must be stated explicitly; otherwise the space accounting for Theorem 5 is incomplete.","section":"Section 8, final paragraph"}],"minor_comments":[{"comment":"The sentence 'Combining this with Lemmas 1, 6, and 5' appears to contain an incorrect lemma reference; Lemma 5 is the reducible-PLCP lemma, and the BPS construction is Lemma 7. It should likely read 'Lemmas 1, 6, and 7'.","section":"Section 8, final paragraph"},{"comment":"The word 'optput' appears twice in the statements of Lemmas 6 and 7 and should be 'output'.","section":"Lemmas 6 and 7"},{"comment":"In the complexity analysis of Algorithm 2, the text says that 'in Line 13 we output R−L−2 LCP values', but the loop in Algorithm 2 outputs LCP[L+1..R], which is R−L values; the formula should be corrected.","section":"Section 5, proof of Lemma 3"},{"comment":"The statement that 'explicit suffix tree nodes correspond to right-maximal substrings' is true only for internal nodes, since leaves are explicit nodes but not right-maximal. This terminology ambiguity is directly related to the Section 8 gap and should be clarified throughout the paper.","section":"Section 3"},{"comment":"The phrase 'using the FL function on the BWT' appears to refer to the LF mapping used to walk suffixes in text order; the nonstandard name 'FL' should be corrected or defined.","section":"Section 7"}],"recommendation":"major_revision","confidential_remarks":"The stress-test concern about Section 8 is correct and central: the BPS construction as written does not build a suffix tree topology because leaf intervals are missing. This should be the main point for the authors to fix. I am otherwise favorably inclined toward the paper; the LCP and PLCP parts are careful, and the BWT-merging contribution is valuable. Once the leaf-interval issue and the CSA space accounting are addressed, I would be willing to accept."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Good to get your read on this one. My take: the LCP and PLCP constructions are genuinely valuable and mostly convincing, but the BPS topology construction in Section 8 has a real gap that blocks the headline CST claim.\n\nWhat's new: the paper gives the first succinct-space (o(n log σ) bits on top of the BWT) enumeration of LCP values and suffix tree intervals, using a neat combination of Belazzougui's stack-based enumeration and Beller's queue-based induction. The block-based PLCP bitvector construction is clever and the complexity accounting checks out. The BWT merge algorithm in Section 9 is also a solid improvement over Belazzougui et al., and the experiments show practical throughput. Credit where due: the LCP and PLCP proofs are detailed and generally sound. The paper is careful about space.\n\nThe soft spot is Section 8. The construction builds the BPS by incrementing Open[l] and Close[r] for every interval returned by Lemma 4, which enumerates only right-maximal substrings—i.e., internal suffix tree nodes. Leaves are SA intervals [i,i] with no right extension; they are not right-maximal and are never enumerated or added. In the Sadakane BPS representation, every leaf must contribute a pair of parentheses. Omitting the n leaves means the output has about 2·(#internal) bits, not 4n bits, and leaf-oriented operations fail. The paper never mentions adding leaf intervals. For T='ab#', the root interval [1,3] yields '()', not a tree with three leaves. This is fixable—just enumerate the n singleton intervals and update the counters—but it is not a cosmetic tweak; Theorem 5's claimed compressed suffix tree is not built by the described algorithm.\n\nOne smaller issue: Section 6 is titled 'Enumerating Suffix Tree Intervals' but Lemma 4 limits to right-maximal substrings, which conflicts with the topology need. The text should be explicit about leaves.\n\nNet: the LCP/PLCP/merge parts are a genuine contribution. The CST construction needs a clear fix and re-analysis before Theorem 5 can stand. I'd send the paper to a serious referee, but with the expectation of a major revision. If the authors can handle the leaf issue, this is a strong result for the string indexing community; if not, the LCP and merge material still deserves publication.\n\nBring to reading group? Yes—good discussion material. I'd cite the LCP enumeration lemma.","headline":"The LCP and PLCP constructions are solid and the BWT merge is a real contribution, but Section 8's BPS topology construction omits leaf intervals, so Theorem 5's compressed suffix tree claim is not actually proven.","tokens_in":29435,"tokens_out":3070,"would_cite":true,"duration_ms":31736,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W32"],"pacs":[],"model":"deepseek-v4-flash","headline":"A compressed suffix tree can be built directly from the Burrows-Wheeler transform using sublinear working space and near-linear time.","keywords":["Burrows-Wheeler transform","compressed suffix tree","LCP array","PLCP bitvector","balanced parentheses","succinct working space","string collections","BWT merging"],"falsifier":"Take a text with no repeated substrings, such as $T=\\texttt{abcdef}$ plus its terminator, run the Section 8 topology construction, and count the open parentheses in the output: a correct BPS of the suffix tree has at least $n+1$ open parentheses (one per leaf plus the root), whereas an enumeration restricted to right-maximal substrings produces only the root's pair, so leaf-parent or depth operations on any leaf would fail.","tokens_in":28426,"feed_emoji":"🧬","tokens_out":11264,"duration_ms":104022,"temperature":0.7,"pith_summary":"The paper aims to show that all components of a compressed suffix tree—the LCP values, the PLCP bitvector, and the balanced-parentheses topology—can be derived directly from a Burrows-Wheeler transform in working space that is asymptotically smaller than the BWT itself. The key result is parameterized: for any $\\epsilon$, the PLCP bitvector and the suffix tree topology are built in $\\epsilon\\cdot n\\log\\sigma + o(n)$ bits, with time $O(n(\\log\\sigma + \\epsilon^{-1}\\log\\log n))$, and the resulting compressed suffix tree takes $n\\log\\sigma + 6n + o(n\\log\\sigma)$ bits. This closes a gap between previous algorithms, which required either $O(n\\log\\sigma)$ bits with linear time or $O(n)$ bits with $O(n\\log n)$ time. The same techniques merge two BWTs of a string collection in $O(n\\log\\sigma)$ time and $o(n\\log\\sigma)$ bits. If correct, this makes compressed suffix trees buildable for very large genomic collections in almost no extra memory.","feed_headline":"Compressed suffix tree built from BWT in almost no extra space","feed_subtitle":"LCP values, PLCP bitvector, and tree topology all assemble in a tiny, tunable slice of extra bits.","key_machinery":"The machinery has two halves. First, LCP pairs and suffix-tree intervals are enumerated by traversing BWT intervals: from a range $[L,R]$ of a string $W$, the operation `getIntervals` uses a wavelet matrix to list, in $O(\\log\\sigma)$ time each, the new ranges of left-extensions $cW$. Right-maximal substrings—strings followed by at least two distinct characters, which are exactly the internal suffix-tree nodes—are visited via Weiner links, using a stack when the alphabet is small and a queue when it is large, with a threshold that keeps total working space $o(n\\log\\sigma)$. Second, the PLCP bitvector is assembled from irreducible LCP values using the facts that PLCP is almost increasing and that reducible values equal the previous value minus one; the topology is obtained by turning interval endpoints into open/close counters, blockwise, with block size $B=\\epsilon\\cdot n\\log\\sigma/\\log\\log n$.","core_discovery":"The central claim is that, given the word-packed Burrows-Wheeler transform of a text $T$ of length $n$ over alphabet $[1,\\sigma]$ and any $0<\\epsilon\\le 1$, one can replace it with a compressed suffix tree in $O(n(\\log\\sigma + \\epsilon^{-1}\\log\\log n))$ time and $\\epsilon\\cdot n\\log\\sigma + o(n)$ bits of working space, producing a structure of $n\\log\\sigma + 6n + o(n\\log\\sigma)$ bits that supports suffix-tree operations in $O(\\operatorname{polylog} n)$ time. The construction assembles two enumeration procedures: one that outputs all pairs $(i,\\mathrm{LCP}[i])$ and one that outputs all suffix-tree intervals, both in $O(n\\log\\sigma)$ time using $o(n\\log\\sigma)$ bits. Those enumerations feed blockwise computations of the PLCP bitvector and the balanced-parentheses topology, with $\\epsilon$ controlling the space-time trade-off. The same traversal ideas give an $O(n\\log\\sigma)$-time, $o(n\\log\\sigma)$-space algorithm for merging the BWTs of two collections, and an implementation on DNA data uses about $n$ bits on top of a packed BWT while processing about 2.92 megabases per second.","pith_inferences":["The blockwise counter technique suggests a direct external-memory adaptation: choose $B$ so that one block of counters fits in RAM, stream the interval enumeration, and build the topology of arbitrarily large texts within the same space bound.","The same Weiner-link enumeration could supply the child and sibling navigational tables of a compressed suffix tree, so a full CST beyond BPS and PLCP may be constructible within the same $o(n\\log\\sigma)$ space bounds.","The merge algorithm's leaf-pair navigation is naturally generalizable to a multi-collection merge by maintaining one interval pair per collection, yielding a multi-way BWT merge with the same time per character.","Because the space bound is tunable through $\\epsilon$, an implementation could adapt the parameter to available RAM, trading a $\\log\\log n$ factor in time for space as low as $o(n\\log\\sigma)$."],"forward_implications":["The LCP array of a string collection can be induced from the BWT in $O(n\\log\\sigma)$ time using $o(n\\log\\sigma)$ bits, matching the best time bound while using less space.","For any $\\epsilon$, the PLCP bitvector and the BPS topology can be produced in $\\epsilon\\cdot n\\log\\sigma + o(n)$ bits; setting $\\epsilon$ small gives a near-linear-time, succinct-space construction.","A complete compressed suffix tree can replace the BWT in $n\\log\\sigma + 6n + o(n\\log\\sigma)$ bits, with all operations in $O(\\operatorname{polylog} n)$ time.","Two BWTs can be merged into the BWT of their union in $O(n\\log\\sigma)$ time and $o(n\\log\\sigma)$ bits, which also induces the LCP array of the merged collection.","An implementation on DNA alphabets uses as little as $n$ bits on top of the packed input/output and processes data at about 2.92 megabases per second."],"supporting_citations":[{"why":"Supplies the queue-based BWT traversal that enumerates LCP pairs; the paper extends it to string collections and large alphabets.","marker":"[5]"},{"why":"Supplies the Weiner-link enumeration of suffix-tree intervals and node representations used for small alphabets.","marker":"[2]"},{"why":"Provides the wavelet matrix representation of the BWT with rank and range-distinct queries in O(log σ), used as the input data structure.","marker":"[10]"},{"why":"Supplies the almost-increasing property of PLCP that justifies the 2n-bit bitvector representation.","marker":"[24]"},{"why":"Supplies the lemma that reducible PLCP values equal the preceding value minus one, used to fill the PLCP bitvector.","marker":"[29]"},{"why":"Supplies the bound on the total of irreducible LCP values that keeps the large-LCP table sublinear.","marker":"[23]"},{"why":"Defines the compressed suffix tree (CSA, PLCP, BPS) that the construction targets.","marker":"[41]"},{"why":"Stores the previous BWT-merging space-time trade-off that Theorem 6 improves.","marker":"[3]"},{"why":"Serves as the experimental baseline for merging BWTs and inducing LCP.","marker":"[13]"}],"fun_headline_variants":["Enumerate LCP and suffix tree intervals in o(n log σ) bits","BWT to PLCP and topology with ε-tunable space","Merge BWTs in O(n log σ) time and o(n log σ) bits","Linear-time LCP enumeration with sublinear memory","Small work space builds compressed suffix tree from BWT"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The topology construction assumes that enumerating intervals of right-maximal substrings and converting each interval's endpoints into open/close counters yields the full balanced-parentheses suffix tree, without separately adding the $n$ singleton leaf intervals corresponding to text positions.","fun_headline_variants_meta":{"raw":{"variants":["Enumerate LCP and suffix tree intervals in o(n log σ) bits","BWT to PLCP and topology with ε-tunable space","Merge BWTs in O(n log σ) time and o(n log σ) bits","Linear-time LCP enumeration with sublinear memory","Small work space builds compressed suffix tree from BWT"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001815,"raw_usage":{"total_tokens":7242,"prompt_tokens":1145,"completion_tokens":6097,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":761,"completion_tokens_details":{"reasoning_tokens":6007}},"tokens_in":761,"tokens_out":6097,"duration_ms":40868,"temperature":1.0,"reasoning_tokens":6007,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T13:55:15.253076+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a text with no repeated substrings, such as $T=\\texttt{abcdef}$ plus its terminator, run the Section 8 topology construction, and count the open parentheses in the output: a correct BPS of the suffix tree has at least $n+1$ open parentheses (one per leaf plus the root), whereas an enumeration restricted to right-maximal substrings produces only the root's pair, so leaf-parent or depth operations on any leaf would fail.","supporting_citations":[{"cited_title":"Beller, S","cited_arxiv_id":null,"evidence_quote":"Supplies the queue-based BWT traversal that enumerates LCP pairs; the paper extends it to string collections and large alphabets."},{"cited_title":"Belazzougui","cited_arxiv_id":null,"evidence_quote":"Supplies the Weiner-link enumeration of suffix-tree intervals and node representations used for small alphabets."},{"cited_title":"Claude, G","cited_arxiv_id":null,"evidence_quote":"Provides the wavelet matrix representation of the BWT with rank and range-distinct queries in O(log σ), used as the input data structure."},{"cited_title":"Kasai, G","cited_arxiv_id":null,"evidence_quote":"Supplies the almost-increasing property of PLCP that justifies the 2n-bit bitvector representation."},{"cited_title":"Two space saving tricks for linear ti me lcp array computation","cited_arxiv_id":null,"evidence_quote":"Supplies the lemma that reducible PLCP values equal the preceding value minus one, used to fill the PLCP bitvector."},{"cited_title":"K¨ arkk¨ ainen, G","cited_arxiv_id":null,"evidence_quote":"Supplies the bound on the total of irreducible LCP values that keeps the large-LCP table sublinear."},{"cited_title":"Sadakane","cited_arxiv_id":null,"evidence_quote":"Defines the compressed suffix tree (CSA, PLCP, BPS) that the construction targets."},{"cited_title":"Linear-time string indexing and analysis in small space","cited_arxiv_id":"1609.06378","evidence_quote":"Stores the previous BWT-merging space-time trade-off that Theorem 6 improves."},{"cited_title":"Egidi and G","cited_arxiv_id":null,"evidence_quote":"Serves as the experimental baseline for merging BWTs and inducing LCP."}],"review_version":1}