{"id":"9226d3df-dd9d-45b4-b2b9-a45f2d79206f","arxiv_id":"1908.09125","paper_version":3,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"A string position is 'nice' if inserting the sentinel $ there yields a valid BWT image; the paper characterizes nice positions via pseudo-cycles of the standard permutation and computes them in O(n log n) time.","lead":"This paper asks where a dollar sign can be inserted into a string so that the result is the Burrows-Wheeler transform of some word. It gives a complete combinatorial answer in terms of the standard permutation and an O(n log n) algorithm to find all such positions.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Central claim rests on cited BWT-image criterion not rederived for sentinel alphabets; Corollary 2's bridge is the only unproven dependency.","rationale":"The reader's verdict is sound. I checked the main chain: Corollary 2 follows from Theorem 2 plus the observation that a single-$ BWT image can be rotated to end with $; Lemma 2 maintains σ_{i+1} correctly; Lemma 3 supplies the split/merge cycle update; and the splay-tree implementation matches the two required operations. Thus Algorithm 1 is correct if Corollary 2 holds. Theorem 6 is a direct consequence of Lemma 4, and the small exhaustive tables provide supporting evidence. The genuinely load-bearing dependency is the external Likhomanov–Shur criterion, which the paper cites but does not rederive. I would also flag a textual defect in Corollary 1: its displayed cycle form appears to have an indexing error, since for w=bbaa with c=2 and m=2 the printed cycles would contain more than n elements. However, Corollary 1 is used only in Theorem 5 and is not needed for Corollary 2 or Algorithm 1, so this does not affect the central claim. The absence of released code is an availability issue rather than a correctness issue. Overall, the concern about Theorem 2 is real but external; the proposed brute-force check would settle whether it actually lands.","tokens_in":35654,"tokens_out":25548,"duration_ms":267451,"concrete_test":"Write a brute-force verifier that enumerates all binary words w of length n≤8 and all insertion positions i; for each dol(w,i), compute σ_i and the runlength gcd, and independently decide niceness by constructing all rotations of every candidate v$, sorting them, and checking whether the last column equals dol(w,i). Then verify the equivalence: i is nice iff σ_i is cyclic. Any mismatch would pinpoint whether the cited Theorem 2 fails for sentinel strings.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Every main result—Corollary 2, Theorem 6, and Algorithm 1—depends on the same bridge: dol(w,i) is in BWT(Σ*_$) iff σ_i is cyclic. The forward direction needs Theorem 2 of [28] to apply to the extended alphabet Σ∪{$}, and the reverse direction additionally needs the unstated fact that a single-$ BWT image of a primitive word can be rotated so that $ is last without changing the BWT. The paper cites Theorem 2 but does not prove it, and the sentinel application is asserted rather than argued. If that criterion has a hidden primitivity or alphabet condition, both the pseudo-cycle characterization and the O(n log n) algorithm collapse. I found no internal error downstream of this gate; the splay-tree split/merge logic and Lemma 4 are consistent with the small exhaustive tables. A separate textual defect is Corollary 1's displayed cycle form (e.g., for w=bbaa, c=2, m=2, the formula as printed would yield cycles with more than n elements); since Corollary 1 is used only for Theorem 5 and not for Corollary 2 or Algorithm 1, it does not threaten the central claim but should be corrected.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the following question: given a word w over an ordered alphabet, for which insertion positions i does inserting the sentinel $ turn w into the BWT of some word ending with $? Such positions are called nice. The authors show that niceness depends only on the standard permutation of w, give a combinatorial characterization of nice positions in terms of pseudo-cycles, present an O(n log n)-time algorithm based on splay trees, and derive bounds on the number and value of nice positions. They also provide extensive experimental statistics for binary and ternary alphabets up to length 20.","tokens_in":35858,"tokens_out":20277,"duration_ms":214076,"significance":"If the central results are correct, the paper makes a solid contribution to the combinatorial theory of the BWT: it gives the first non-quadratic algorithm for the Dollar-BWT problem and an elegant structural characterization of the answer. The pseudo-cycle notion is natural, the splay-tree data structure is appropriate for maintaining cycle splits and merges, and the exhaustive verification for all binary strings up to length 20 and ternary strings up to length 20 is a genuine strength. The parity theorem and the lower bounds on nice positions are additional useful results. However, two load-bearing points in the written proofs need repair before the claims can be accepted as stated.","major_comments":[{"comment":"Lemma 4 is false as stated. The forward direction claims that if S is a pseudo-cycle then shift(S,i) is a single cycle in σ_i. The proof only establishes that shift(S,i) is invariant under σ_i, which does not imply that it is one cycle. Counterexample: take σ = (1 2)(3)(4) and S = {2,4}, with Sleft = {2} and Sright = {4}. Then S is a pseudo-cycle with critical interval [3,4]. For i = 3, shift(S,3) = {2,5}, while σ_3 = (1 3)(2)(4)(5), so shift(S,3) is a union of two fixed points, not a cycle. Since Theorem 6 invokes Lemma 4 in both directions, the proof of the main characterization is not valid as written. The theorem can be repaired by weakening the forward direction to 'shift(S,i) is a nonempty proper σ_i-invariant set', which is enough to show σ_i is not cyclic; the reverse direction (a cycle not containing i gives a pseudo-cycle) is correct. The lemma and its proof should be rewritten accordingly.","section":"Section 4, Lemma 4"},{"comment":"The inference 'i is nice if and only if σ_i is cyclic' is not immediate from Theorem 2 of [28] as printed. One must first note that dol(w,i) contains exactly one $, so the gcd of its runlengths is 1. Second, one must justify that if a word over the extended alphabet Σ∪{$} with exactly one $ is a BWT image, then some conjugate with $ at the end has the same BWT; this is an elementary but non-obvious fact (for primitive words the BWT is invariant under taking conjugates). Neither point is stated in the paper. Because Corollary 2 is the bridge from the cited characterization to Theorem 6 and Algorithm 1, a short lemma proving both facts should be added.","section":"Section 2.4, Corollary 2"},{"comment":"The displayed cycle form in Corollary 1 is wrong as written. For w = bbaa, Theorem 1 gives c = 2 and m = 2, but the formula would produce cycles such as (1,3,4) and (2,4,5), which have more than n elements and contain 5 outside {1,2,3,4}; the actual standard permutation is (1,3)(2,4). Since Theorem 5 derives the form of σ_{c+1} from this formula, the proof of Theorem 5 needs to be rewritten using the correct cycle form. This error does not affect Algorithm 1 or Theorem 6, but it is a substantive mathematical error in a stated theorem and its proof.","section":"Section 2.4, Corollary 1 and Section 4, Theorem 5"}],"minor_comments":[{"comment":"The printed standard permutation σ = (1,3,4,5,3) is not a permutation; it has a duplicate 3 and omits 2. Please correct this entry.","section":"Table 4, row for w = babba"},{"comment":"The cycle notation in these examples contains repeated printed groups such as '(1 1 1 1)', which appear to be a typesetting or conversion artifact; the displayed permutations should be checked so that each element appears exactly once.","section":"Examples 1, 5, and 6"},{"comment":"The update in lines 20–21 reads σ(i+1) before overwriting σ(i+1); the pseudocode should state explicitly that the old value of σ(i+1) is used in the first assignment, since the order of in-place assignments is essential.","section":"Algorithm 1, procedure Update"},{"comment":"After the lemma is weakened as suggested in the major comment, the proof should include an explicit cardinality argument: from U ⊆ σ_i(U) and injectivity of σ_i it follows that σ_i(U) = U, so U is a union of cycles, not necessarily one cycle.","section":"Section 4, proof of Lemma 4"}],"recommendation":"major_revision","confidential_remarks":"The central algorithm and the pseudo-cycle characterization appear salvageable, and the empirical work is convincing. The main obstacle is the false Lemma 4, which is used in the proof of Theorem 6; the paper should not be accepted until that lemma is corrected or replaced by the weaker invariant-set statement. The missing justification in Corollary 2 is easy to repair but should not be left implicit, since the whole paper rests on that bridge."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is a legitimate new result, not a repackaged BWT observation. The paper characterizes exactly where you can insert a single $ into a word so that the result is the BWT of a word ending with $, and it gives an O(n log n) algorithm. I went looking for the load-bearing flaw and did not find one.\n\nWhat is new: the pseudo-cycle characterization (Theorem 6) and the splay-tree algorithm (Algorithm 1). Lemma 4 is the key technical step, and it is proven cleanly: cycles in the shifted permutation correspond exactly to pseudo-cycles in the original standard permutation with the insert position in the critical interval. The algorithm's cycle split/merge update is standard but applied correctly, and the amortized analysis via Sleator-Tarjan is sound. The paper also gives parity, upper bounds, and exhaustive tables for small alphabets, which makes the empirical side useful rather than decorative.\n\nThe soft spots are minor. The central dependency is Theorem 2 of Likhomanov-Shur: BWT image iff the number of cycles equals the gcd of the runlengths. The paper uses it to get Corollary 2, that with exactly one $, nice iff cyclic. Since a word with one $ has a run of length 1, the gcd is automatically 1, so the corollary really is just a one-line application. I checked the stress-test concern about the sentinel alphabet and I think it does not land: nothing in the cited theorem seems to exclude an alphabet that contains a smallest sentinel character, and the paper's use is standard. It would still be good for the authors to explicitly say the theorem is being applied to the extended alphabet rather than silently doing it.\n\nThere is a genuine typo in Corollary 1's displayed cycle form: as printed, the cycles have the wrong length. It is used only in Theorem 5, not in the main characterization or algorithm, so it is a correction-not-a-catastrophe, but it should be fixed. Also, the implementation from Section 6 is not released, which is a small reproducibility gap, not a substantive one.\n\nThis paper deserves a serious referee. The proofs are hand-checkable, the central idea is new, and the algorithm works. I would accept it after minor revisions.\n\nRecommendation: send it to review, with a referee who knows BWT combinatorics, and ask them to verify Theorem 2's applicability and clean up Corollary 1.","headline":"A genuinely new and correct combinatorial characterization of dollar-insertion positions in BWT images, with a sound O(n log n) algorithm; the only real dependency is a cited external theorem that I believe applies.","tokens_in":36396,"tokens_out":3580,"would_cite":true,"duration_ms":40018,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68R15","05A05"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that the positions where inserting the sentinel $ makes a word w a BWT image are exactly the positions outside the union of critical intervals of pseudo-cycles of w's standard permutation, and computes them in O(n log n)…","keywords":["Burrows-Wheeler transform","BWT images","sentinel character","standard permutation","pseudo-cycle","combinatorics on words","splay trees","Dollar-BWT problem"],"falsifier":"For any word w, compute σw, list every pseudo-cycle and its critical interval, and mark the union of critical intervals; then compare the resulting set with the naive test that runs the BWT reversal algorithm on dol(w,i) for every i. A single position where the two answers disagree would refute Theorem 6 and, with it, the algorithmic claim.","tokens_in":35468,"feed_emoji":"💵","tokens_out":6763,"duration_ms":64205,"temperature":0.7,"pith_summary":"The paper asks a precise question about the Burrows-Wheeler transform: given any word w, at which positions can the sentinel character $ be inserted so that the resulting string is the BWT image of some word ending with $? Such positions are called nice. The paper establishes that niceness depends only on the standard permutation of w, and gives a complete characterization: i is nice exactly when no pseudo-cycle of that permutation has its critical interval containing i. It also gives an O(n log n) algorithm that finds all nice positions, improving the naive quadratic procedure, and proves structural bounds such as parity and upper bounds on the number of nice positions. The characterization matters because sentinel-terminated BWT is the standard form used in text indexing and bioinformatics tools, where deciding whether a candidate string can be a BWT image is a basic feasibility check.","feed_headline":"Nice positions are exactly the gaps no pseudo-cycle covers","feed_subtitle":"A single permutation walk replaces the quadratic per-position test for sentinel BWT images.","key_machinery":"The carrying objects are the standard permutation σw of w, which lists positions by character order and breaks ties by increasing index, and the pseudo-cycles with their critical intervals just defined. On top of these, the algorithmic mechanism is Lemma 2: moving the insertion point from i to i+1 changes the standard permutation by a single transposition, so the cycle count either splits or merges; deciding which happens reduces to asking whether i+1 lies in the cycle containing i. A forest of splay trees represents the cycles of the current permutation and supports that membership test, split, and merge in amortized logarithmic time, giving the O(n log n) bound.","core_discovery":"The central result is Theorem 6: for a word w of length n and any 1≤i≤n+1, position i is nice if and only if no pseudo-cycle of the standard permutation σw has its critical interval containing i. A pseudo-cycle is a nonempty subset S of positions that splits into a left part Sleft and a right part Sright, all left positions smaller than all right ones, with σw(S) = (Sleft−1) ∪ Sright; its critical interval runs from one after the largest left element to the smallest right element. So the nice positions are exactly the complement of the union of all critical intervals of pseudo-cycles. Algorithm 1 starts from σ1 and moves to σn+1 by one transposition per step, maintaining the number of cycles in a splay-tree forest and reporting every position where the count becomes 1; this runs in O(n log n) time and O(n) space. The paper also proves that every BWT image has at least one nice position, that all nice positions have the same parity, and explicit lower bounds on their values.","pith_inferences":["The pseudo-cycle characterization suggests that nice positions can be decided independently per position from a precomputed description of critical intervals; an output-sensitive or O(n) algorithm may be possible if those intervals can be represented compactly, which the paper leaves open.","The same \"insert one distinguished character and ask whether the result is valid\" test could be applied to other string data structures such as suffix arrays or Wheeler graphs; the pseudo-cycle notion might transfer as a local obstruction there too.","Because the algorithm's correctness rests on the cycle-count test for BWT images, any future strengthening or weakening of that external characterization would directly change the set of nice positions; the parity and bound results would be the first to show a discrepancy.","The statistics in the paper hint that for most strings over larger alphabets there are few nice positions; a plausible testable conjecture is that h(w) is O(log n) for random words, though this is not claimed in the paper."],"forward_implications":["All nice positions of a word can be enumerated in O(n log n) time and O(n) space, compared with the straightforward O(n^2) per-position inversion check.","If a word w is already a BWT image with c cycles in its standard permutation, then position c+1 is always nice, so every BWT image admits at least one dollar insertion.","All nice positions share the same parity: if the number of cycles of σw is even, every nice position is odd, and vice versa; consequently h(w) ≤ floor((n+1)/2).","Any nice position must be at least max{L+1, 2b+c}, where L is the largest minimum element among cycles and b is the number of bad pairs; these bounds can seed a faster heuristic start for the algorithm.","A position is bad exactly when some pseudo-cycle covers it, so the word banana has no nice position because its pseudo-cycle critical intervals cover every candidate insertion point."],"supporting_citations":[{"why":"Supplies the characterization of BWT images by equality of cycle count and gcd of runlengths, which Corollary 2 turns into the 'nice iff cyclic' criterion.","marker":"[28]"},{"why":"Proves the BWT-image characterization for binary alphabets and the structure theorem for powers used in Corollary 1.","marker":"[32]"},{"why":"Defines the BWT and its reversal algorithm, which is the naive per-position test the new algorithm improves and the correctness reference for BWT images.","marker":"[4]"},{"why":"Provides the splay-tree operations and the amortized logarithmic bound used to maintain cycles in the O(n log n) algorithm.","marker":"[41]"},{"why":"Used for the linear-time computation of the standard permutation via counting sort.","marker":"[7]"}],"fun_headline_variants":["Pseudo-cycles pick where dollar makes a BWT","Dollar slots: pseudo-cycle intervals decide","Find BWT dollar slots in O(n log n)","Critical intervals tell where the dollar goes","One walk through permutations finds dollar gaps"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole result depends on an earlier characterization of BWT images: a word is a valid BWT image precisely when the cycle count of its standard permutation equals the greatest common divisor of its run lengths; if that characterization fails for strings containing $, the pseudo-cycle test and the algorithm collapse.","fun_headline_variants_meta":{"raw":{"variants":["Pseudo-cycles pick where dollar makes a BWT","Dollar slots: pseudo-cycle intervals decide","Find BWT dollar slots in O(n log n)","Critical intervals tell where the dollar goes","One walk through permutations finds dollar gaps"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001184,"raw_usage":{"total_tokens":4904,"prompt_tokens":972,"completion_tokens":3932,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":588,"completion_tokens_details":{"reasoning_tokens":3863}},"tokens_in":588,"tokens_out":3932,"duration_ms":28456,"temperature":1.0,"reasoning_tokens":3863,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T11:21:57.247079+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For any word w, compute σw, list every pseudo-cycle and its critical interval, and mark the union of critical intervals; then compare the resulting set with the naive test that runs the BWT reversal algorithm on dol(w,i) for every i. A single position where the two answers disagree would refute Theorem 6 and, with it, the algorithmic claim.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the characterization of BWT images by equality of cycle count and gcd of runlengths, which Corollary 2 turns into the 'nice iff cyclic' criterion."},{"cited_title":"Mantaci, A","cited_arxiv_id":null,"evidence_quote":"Proves the BWT-image characterization for binary alphabets and the structure theorem for powers used in Corollary 1."},{"cited_title":"Burrows and D","cited_arxiv_id":null,"evidence_quote":"Defines the BWT and its reversal algorithm, which is the naive per-position test the new algorithm improves and the correctness reference for BWT images."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the splay-tree operations and the amortized logarithmic bound used to maintain cycles in the O(n log n) algorithm."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Used for the linear-time computation of the standard permutation via counting sort."}],"review_version":1}