When a Dollar Makes a BWT

Francesco Masillo; Romeo Rizzi; Sara Giuliani; Zsuzsanna Lipt\'ak

REVIEW 3 major objections 4 minor 42 references

When a Dollar Makes a BWT

T0 review · 3 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

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

Pith's one-line read 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)…

desk verdict 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. read the letter →

arxiv 1908.09125 v3 pith:CL3SADZS submitted 2019-08-24 cs.DS

Sara Giuliani , Zsuzsanna Lipták , Francesco Masillo , Romeo Rizzi This is my paper · ORCID

classification cs.DS MSC 68R1505A05

keywords Burrows-WheelertransformBWTimagessentinelcharacterstandardpermutationpseudo-cyclecombinatoricsonwordssplaytreesDollar-BWTproblem

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 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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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.

Reading between the lines

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

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.

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, and a circularity audit.

Desk Editor's Note

read the 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.

What 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.

The 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.

There 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.

This 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.

Recommendation: 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.

Referee Report

3 major / 4 minor

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.

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 (3)

[Section 4, Lemma 4] 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 2.4, Corollary 2] 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 2.4, Corollary 1 and Section 4, Theorem 5] 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.

minor comments (4)

[Table 4, row for w = babba] 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.
[Examples 1, 5, and 6] 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.
[Algorithm 1, procedure Update] 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 4, proof of Lemma 4] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: Corollary 2 applies an external BWT-image criterion, and the pseudo-cycle characterization is proved directly from the shift dynamics of σ_i.

full rationale

The derivation chain is not circular in any of the flagged senses. Corollary 2 reduces niceness to cyclicity of σ_i by combining the external Likhomanov–Shur theorem (Theorem 2) with the observation that dol(w,i) contains exactly one $, so the gcd of its runlengths is 1. That is an application of an independent prior theorem, not a definitional identification. Lemma 4 then proves, by explicit case analysis on positions less than and greater than i, that cycles of σ_i correspond exactly to pseudo-cycles of σ_w whose critical interval contains i; Theorem 6 uses both directions of Lemma 4. Pseudo-cycles are defined independently of the predicate 'nice', and the equivalence is proven rather than assumed. Algorithm 1 is a direct implementation of the criterion 'σ_i is cyclic', with cycle-count updates justified by Lemma 3; no parameter is fitted and no output is fed back as an input. The only self-citation is the note that the paper is an extended version of an ICTCS 2019 paper by the same authors, which is not load-bearing. The dependence on Theorem 2 of Likhomanov and Shur is an external assumption and therefore a correctness/scope risk if the sentinel extension were invalid, but importing an external theorem is not circularity. A separate displayed-form issue in Corollary 1 is a correctness defect, not a circular step, and Corollary 1 is not used for Corollary 2 or Algorithm 1.

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

No free parameters are fitted; the central claim depends only on the standard permutation, which is computed exactly. The paper relies on standard prior results (Likhomanov-Shur characterization of BWT images, BWT inversion, splay tree balance theorem) and on standard permutation facts. No new physical or algorithmic entities are postulated beyond the defined notion of pseudo-cycle, which is a mathematical structure rather than an entity requiring independent evidence.

assumptions (6)

domain assumption Theorem 2 of Likhomanov and Shur (2011): w is a BWT image iff the number of cycles of its standard permutation σ_w equals the gcd of the runlengths of w.
Used to derive Corollary 2 (i nice iff σ_i is cyclic), which is the basis for both the characterization (Theorem 6) and the algorithm. Appears in Section 2.4.
domain assumption BWT reversal algorithm: given a BWT image, the original word can be recovered in linear time, uniquely up to rotation; for words ending in $, uniquely.
Background for the problem statement and for the naive O(n^2) method mentioned in Section 3.
standard math Sleator-Tarjan Balance Theorem with Updates: m splay-tree operations on initially empty trees take O(m + Σ log n_j) amortized time.
Invoked in Section 3.3 as Theorem 3 to conclude the algorithm runs in O(n log n).
standard math Counting sort can compute the standard permutation of a string over an ordered alphabet in linear time.
Used in Algorithm 1 and described in Algorithm 2.
domain assumption Every word in Σ*_$ is primitive, so its BWT has distinct rotations and a unique inverse.
Justifies that a word with exactly one $ has a unique preimage if it is a BWT image; used in the problem statement.
standard math Standard permutation properties: cycle decomposition, sign of a permutation, and the effect of multiplying by a transposition (splitting or merging cycles).
Used throughout, especially Lemma 3.

how reviews work

0 comments

Cite this review

Pith. "Pith review of When a Dollar Makes a BWT." pith.science (2026). https://pith.science/paper/CL3SADZS

@misc{pith2026190809125,
  author       = {Pith},
  title        = {Pith review of: When a Dollar Makes a BWT},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/CL3SADZS}},
  note         = {Machine review of arXiv:1908.09125}
}

read the original abstract

The Burrows-Wheeler-Transform (BWT) is a reversible string transformation which plays a central role in text compression and is fundamental in many modern bioinformatics applications. The BWT is a permutation of the characters, which is in general better compressible and allows to answer several different query types more efficiently than the original string. It is easy to see that not every string is a BWT image, and exact characterizations of BWT images are known. We investigate a related combinatorial question. In many applications, a sentinel character dollar is added to mark the end of the string, and thus the BWT of a string ending with dollar contains exactly one dollar-character. Given a string w, we ask in which positions, if any, the dollar-character can be inserted to turn w into the BWT image of a word ending with dollar. We show that this depends only on the standard permutation of w and present a O(n log n)-time algorithm for identifying all such positions, improving on the naive quadratic time algorithm. We also give a combinatorial characterization of such positions and develop bounds on their number and value. This is an extended version of [Giuliani et al. ICTCS 2019].

Figures

Figures reproduced from arXiv: 1908.09125 by the authors.

**Figure 1.** BWT of the strings banana, nanana and nanana$. BWT image w, a word v such that BWT(v) = w can be found in linear time in the length of w, and v is unique up to rotation [4]. The BWT is defined for every word, even if not all of its rotations are distinct; this is the case, for example, with the word nanana, whose BWT is nnnaaa, see [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

42 extracted references · 42 canonical work pages

[28]

K. M. Likhomanov and A. M. Shur. Two Combinatorial Crite ria for BWT Images. In Proceeding of the 6th International Computer Science Symposium in Russia (CSR 2011) , pages 385–396, 2011

work page 2011
[1]

Bannai, S

H. Bannai, S. Inenaga, A. Shinohara, and M. Takeda. Infer ring strings from graphs and arrays. In 28th International Symposium on Mathematical Foundations o f Computer Science (MFCS 2003), volume 2747 of Lecture Notes in Computer Science , pages 208–217. Springer, 2003

work page 2003
[2]

M. B´ ona. Combinatorics of Permutations . CRC Press, 2012

work page 2012
[3]

Bonomo, S

S. Bonomo, S. Mantaci, A. Restivo, G. Rosone, and M. Scior tino. Sorting conjugates and suﬃxes of words in a multiset. Int. J. Found. Comput. Sci. , 25(8):1161, 2014

work page 2014
[4]

Burrows and D

M. Burrows and D. J. Wheeler. A block-sorting lossless da ta compression algorithm. Technical report, DIGITAL System Research Center, 1994

work page 1994
[5]

Cazaux and E

B. Cazaux and E. Rivals. Reverse engineering of compact s uﬃx trees and links: A novel algorithm. J. Discrete Algorithms , 28:9–22, 2014

work page 2014
[6]

Cl´ ement, M

J. Cl´ ement, M. Crochemore, and G. Rindone. Reverse engi neering preﬁx tables. In 26th Interna- tional Symposium on Theoretical Aspects of Computer Science ( STACS 2009), pages 289–300, 2009

work page 2009
[7]

T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms . MIT Press, 2009

work page 2009

Show all 42 references

[8]

A. J. Cox, T. Jakobi, G. Rosone, and O. Schulz-Trieglaﬀ. Co mparing DNA sequence collections by direct comparison of compressed text indexes. In Proceedings of the 12th International Workshop Algorithms in Bioinformatics (WABI 2012) , volume 7534, pages 214–224. Springer, 2012

2012
[9]

Crochemore, J

M. Crochemore, J. D´ esarm´ enien, and D. Perrin. A note onthe Burrows-Wheeler transformation. Theoretical Computer Science , 332(1-3):567–572, 2005

2005
[10]

Crochemore, R

M. Crochemore, R. Grossi, J. K¨ arkk¨ ainen, and G. M. Landau. Computing the Burrows-Wheeler transform in place and in small space. J. Discrete Algorithms , 32:44–52, 2015. 24

2015
[11]

F. A. da Louza, T. Gagie, and G. P. Telles. Burrows-Wheel er transform and LCP array con- struction in constant space. J. Discrete Algorithms , 42:14–22, 2017

2017
[12]

J. W. Daykin, F. Franek, J. Holub, A. S. M. S. Islam, and W. F. Smyth. Reconstructing a string from its Lyndon arrays. Theoretical Computer Science , 710:44–51, 2018

2018
[13]

J. W. Daykin, R. Groult, Y. Guesnet, T. Lecroq, A. Lefebv re, M. L´ eonard, and ´E. Prieur- Gaston. A survey of string orderings and their application t o the Burrows–Wheeler transform. Theoretical Computer Science , 710:52–65, 2018

2018
[14]

Ferenczi and L

S. Ferenczi and L. Q. Zamboni. Clustering words and inte rval exchanges. Journal of Integer Sequences, 16(2):3, 2013

2013
[15]

Ferragina, R

P. Ferragina, R. Giancarlo, G. Manzini, and M. Sciortin o. Boosting textual compression in optimal linear time. J. ACM , 52(4):688–713, 2005

2005
[16]

Gagie, G

T. Gagie, G. Manzini, and J. Sir´ en. Wheeler graphs: A fr amework for BWT-based data struc- tures. Theoretical Computer Science , 698:67–78, 2017

2017
[17]

I. M. Gessel and C. Reutenauer. Counting permutations w ith given cycle structure and descent set. Journal of Combinatorial Theory , 64(2):189–215, 1993

1993
[18]

Giancarlo, A

R. Giancarlo, A. Restivo, and M. Sciortino. From ﬁrst pr inciples to the Burrows and Wheeler transform and beyond, via combinatorial optimizat ion. Theoretical Computer Science, 387(3):236–248, 2007

2007
[19]

M. He, J. I. Munro, and S. S. Rao. A categorization theore m on suﬃx arrays with applications to space eﬃcient text indexes. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005) , pages 23–32, 2005

2005
[20]

T. I, S. Inenaga, H. Bannai, and M. Takeda. Inferring str ings from suﬃx trees and links on a binary alphabet. Discrete Applied Mathematics , 163:316–325, 2014

2014
[21]

Kaplan, S

H. Kaplan, S. Landau, and E. Verbin. A simpler analysis o f Burrows–Wheeler-based compres- sion. Theoretical Computer Science , 387(3):220–235, 2007

2007
[22]

Kaplan and E

H. Kaplan and E. Verbin. Most Burrows-Wheeler based com pressors are not optimal. In Annual Symposium on Combinatorial Pattern Matching (CPM 2007) , pages 107–118. Springer, 2007

2007
[23]

K¨ arkk¨ ainen, M

J. K¨ arkk¨ ainen, M. Piatkowski, and S. J. Puglisi. String inference from Longest-Common-Preﬁx Array. In 44th International Colloquium on Automata, Languages, and Pr ogramming (ICALP 2017), pages 62:1–62:14, 2017

2017
[24]

Kucherov, L

G. Kucherov, L. T´ othm´ er´ esz, and S. Vialette. On the combinatorics of suﬃx arrays. Information Processing Letters, 113(22-24):915–920, 2013

2013
[25]

T. W. Lam, R. Li, A. Tam, S. Wong, E. Wu, and S. M. Yiu. High t hroughput short read alignment via bi-directional BWT. In 2009 IEEE International Conference on Bioinformatics and Biomedicine, pages 31–36, 2009. 25

2009
[26]

Langmead, C

B. Langmead, C. Trapnell, M. Pop, and S. L. Salzberg. Ult rafast and memory-eﬃcient alignment of short DNA sequences to the human genome. Genome Biology, 10(3):R25, 2009

2009
[27]

Li and R

H. Li and R. Durbin. Fast and accurate long-read alignme nt with Burrows-Wheeler transform. Bioinformatics, 26(5):589–595, 2010

2010
[29]

Mantaci, A

S. Mantaci, A. Restivo, G. Rosone, F. Russo, and M. Scior tino. On Fixed Points of the Burrows- Wheeler Transform. Fundamenta Informaticae, 154(1-4):277–288, 2017

2017
[30]

Mantaci, A

S. Mantaci, A. Restivo, G. Rosone, and M. Sciortino. An e xtension of the Burrows-Wheeler Transform. Theoretical Computer Science , 387(3):298–312, 2007

2007
[31]

Mantaci, A

S. Mantaci, A. Restivo, G. Rosone, and M. Sciortino. A ne w combinatorial approach to sequence comparison. Theory of Computing Systems , 42(3):411–429, 2008

2008
[32]

Mantaci, A

S. Mantaci, A. Restivo, and M. Sciortino. Burrows–Whee ler transform and Sturmian words. Information Processing Letters , 86(5):241–246, 2003

2003
[33]

G. Manzini. An analysis of the Burrows-Wheeler transfo rm. J. ACM , 48(3):407–430, 2001

2001
[34]

Policriti and N

A. Policriti and N. Prezza. LZ77 computation based on th e run-length encoded BWT. Algo- rithmica, 80(7):1986–2011, 2018

1986
[35]

Prezza, N

N. Prezza, N. Pisanti, M. Sciortino, and G. Rosone. SNPs detection by eBWT positional clustering. Algorithms for Molecular Biology , 14(1):3:1–3:13, 2019

2019
[36]

Restivo and G

A. Restivo and G. Rosone. Burrows-Wheeler transform an d palindromic richness. Theor. Com- put. Sci. , 410(30-32):3018–3026, 2009

2009
[37]

Restivo and G

A. Restivo and G. Rosone. Balancing and clustering of wo rds in the Burrows–Wheeler transform. Theoretical Computer Science , 412(27):3019–3032, 2011

2011
[38]

Rosone and M

G. Rosone and M. Sciortino. The Burrows-Wheeler transf orm between data compression and combinatorics on words. In Conference on Computability in Europe (CiE 2013) , pages 353–364. Springer, 2013

2013
[39]

Sch¨ urmann and J

K. Sch¨ urmann and J. Stoye. Counting suﬃx arrays and str ings. Theoretical Computer Science, 395(2-3):220–234, 2008

2008
[40]

Simpson and S

J. Simpson and S. J. Puglisi. Words with simple Burrows- Wheeler Transforms. Electronic Journal of Combinatorics , 15(1), 2008

2008
[41]

D. D. Sleator and R. E. Tarjan. Self-adjusting binary se arch trees. J. ACM , 32(3):652–686, 1985

1985
[42]

T. A. Starikovskaya and H. W. Vildhøj. A suﬃx tree or not a suﬃx tree? J. Discrete Algorithms, 32:14–23, 2015. 26 APPENDIX In this appendix, we give the algorithm for computing the sta ndard permutation (Algorithm 2), two further examples for Algorithm 1 (Examples 5 and 6), an...

2015

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [28]

K. M. Likhomanov and A. M. Shur. Two Combinatorial Crite ria for BWT Images. In Proceeding of the 6th International Computer Science Symposium in Russia (CSR 2011) , pages 385–396, 2011

work page 2011

[2] [1]

Bannai, S

H. Bannai, S. Inenaga, A. Shinohara, and M. Takeda. Infer ring strings from graphs and arrays. In 28th International Symposium on Mathematical Foundations o f Computer Science (MFCS 2003), volume 2747 of Lecture Notes in Computer Science , pages 208–217. Springer, 2003

work page 2003

[3] [2]

M. B´ ona. Combinatorics of Permutations . CRC Press, 2012

work page 2012

[4] [3]

Bonomo, S

S. Bonomo, S. Mantaci, A. Restivo, G. Rosone, and M. Scior tino. Sorting conjugates and suﬃxes of words in a multiset. Int. J. Found. Comput. Sci. , 25(8):1161, 2014

work page 2014

[5] [4]

Burrows and D

M. Burrows and D. J. Wheeler. A block-sorting lossless da ta compression algorithm. Technical report, DIGITAL System Research Center, 1994

work page 1994

[6] [5]

Cazaux and E

B. Cazaux and E. Rivals. Reverse engineering of compact s uﬃx trees and links: A novel algorithm. J. Discrete Algorithms , 28:9–22, 2014

work page 2014

[7] [6]

Cl´ ement, M

J. Cl´ ement, M. Crochemore, and G. Rindone. Reverse engi neering preﬁx tables. In 26th Interna- tional Symposium on Theoretical Aspects of Computer Science ( STACS 2009), pages 289–300, 2009

work page 2009

[8] [7]

T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms . MIT Press, 2009

work page 2009