Decomposing Words for Enhanced Compression: Exploring the Number of Runs in the Extended Burrows-Wheeler Transform

Ana\"is Denis; Bastien Cazaux; Florian Ingels

Decomposing Words for Enhanced Compression: Exploring the Number of Runs in the Extended Burrows-Wheeler Transform

T0 review · 0 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read The number of runs in the extended Burrows-Wheeler transform of a word depends heavily on how the word is split into pieces: the worst-to-best ratio is unbounded, while the best split is bounded independent of word length.

desk verdict A new and correct set of bounds for decomposition choice in eBWT compression; the only suspected gap in the cycle construction closes on inspection. read the letter →

arxiv 2506.04926 v1 pith:ADCRNBFS submitted 2025-06-05 cs.DS cs.DMcs.FL

Florian Ingels , Anaïs Denis , Bastien Cazaux This is my paper

classification cs.DScs.DMcs.FL MSC 68R1505A15

keywords Burrows-Wheelertransformextendedworddecompositionscombinatoricsonwordsrunsrun-lengthencodingk-restrictedgeneralizedFibonaccinumbers

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 studies a natural knob in extended Burrows-Wheeler transform (eBWT) compression: a word can be cut into pieces, and the eBWT is applied to the multiset of pieces rather than to the word itself. It proves that the number of valid $k$-restricted decompositions grows exponentially, so exhaustive search is hopeless. At the same time, it proves a positive result: for any $k$, the best $k$-restricted decomposition yields at most $\sigma^{k+1}+4k+2$ runs, a bound independent of word length. The central negative result is that the worst-to-best ratio of run counts is unbounded: for any $k$ and any target $M$, some word admits a $k$-restricted decomposition with maximal run count $|w|-1$. These results frame an open optimization problem: find the decomposition that minimizes eBWT runs, if an efficient algorithm exists.

What carries the argument

The load-bearing machinery is the cycle structure of eBWT inversion: rows of the eBWT matrix are paired by a permutation on letter occurrences, and each cycle reconstructs one string of the multiset. For $L=(ba)^n$ with $F=a^n b^n$, any potential cycle of length $k$ must satisfy the linear system $n\mathbf{t}+\mathbf{i}=2S\mathbf{i}-S\mathbf{t}$, where $S$ is a circulant shift matrix; the paper computes the inverse of $2S-I$ explicitly as $\frac{1}{2^k-1}C(1,2,\dots,2^{k-1})$. Choosing $n\equiv 0\pmod{\prod_{k'=2}^{k}(2k'-1)}$ forces the index solution to be non-integral, so no cycle of length $\le k$ survives. The complement is Theorem 2's bound, which uses the fact that the eBWT of all length-$p$ strings has exactly $\sigma^p$ runs, plus a deletion lemma showing that removing one string changes a run count by at most $2|w|$.

What would settle it

For a fixed $k$, choose $n\equiv 0 \pmod{\prod_{k'=2}^{k}(2k'-1)}$, e.g. $k=3$ with $n=15$, invert the eBWT of $(ba)^n$ by following the F/L cycles, and check whether every reconstructed string has length greater than $k$. The appearance of any cycle of length $\le k$ would disprove the claim; conversely, verifying this for large $n$ would support it. A more search-based falsification would brute-force all decompositions of the concatenation $w=(ba)^n$ for small $n$ and compare $\max/\min$ run counts.

Watch

Extended reading notes

Core claim

The paper establishes three facts. First, the number of $k$-restricted decompositions of a length-$n$ word over an alphabet of size $\sigma$ is a generalized Fibonacci number $G^{k+1}_{n-(k+1)}$, growing exponentially in $n$ (Theorem 1). Second, for every word the minimum over $k$-restricted decompositions satisfies $\min_{W\in D_k(w)}\rho(W)\le \sigma^{k+1}+4k+2$ (Theorem 2); the proof cuts the word into blocks of length $k+1$, bounds the eBWT of the set of all length-$(k+1)$ strings, and removes the leftover block at a cost of at most $2(k+1+r)$ runs. Third, the worst-to-best ratio is unbounded: for any $k$, infinitely many $n$ make the eBWT inverse of $(ba)^n$ consist entirely of strings longer than $k$, giving a decomposition whose eBWT has $|w|-1$ runs while the best decomposition has the bounded value (Theorem 3, Section 6). These results transfer the known run-ratio phenomena between standard BWT and bijective BWT to arbitrary decomposition choices.

Load-bearing premise

The Section 6 construction assumes its linear system (2) captures every possible cycle of length at most $k$ in the eBWT inversion of $(ba)^n$, including the requirement that every cycle starts with an $a$ and ends with a $b$; if some cycle shape escapes this representation, the promised infinite family of $k$-restricted decompositions may not exist.

Editorial extensions

If this is right

Brute force is off the table: $k$-restricted decompositions are exponentially many even with the simplest size constraint.
Any future search algorithm can aim for a target of $\sigma^{k+1}+4k+2$ runs; the optimum cannot be larger, regardless of document length.
An arbitrary decomposition can be catastrophically worse than the original transform, since infinitely many words have a decomposition hitting the maximum possible run count.
The known unbounded run-ratio between standard BWT and bijective BWT ($k=0$ case) is a special case of a general phenomenon for all $k$.
For text indexing and compression pipelines built on eBWT, choosing the decomposition is as important as the transform itself.

Reading between the lines

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

If the optimization problem is ever shown tractable, the $\sigma^{k+1}$ term suggests the cost of exact search would scale exponentially in $k$ and alphabet size but not in document length, pointing toward parameterized algorithms.
The modular construction is tied to a number-theoretic structure (the primitive-root condition for $(ba)^n$ to be a single BWT antecedent), so the difficulty of the decomposition problem may vary with arithmetic properties of $n$, not just combinatorics.
The circulant-matrix technique for excluding short cycles should generalize to other periodic strings whose eBWT has a regular shape, possibly giving lower bounds on run counts for any decomposition of those words.
A testable extension: for random words, the expected ratio between a random decomposition and the best decomposition could be measured empirically; the paper's worst-case result suggests variance may be high even when the average is mild.

Share X Bluesky LinkedIn Reddit HN

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

Quick take: this is a solid theory paper, not a breakthrough but a genuinely new problem with correctly proven bounds. The reader's one worry about Section 6 does not survive a close look: every cycle in the eBWT of (ba)^n must contain an a->b transition (pure a-cycles force 2^l i = i, pure b-cycles strictly decrease the index), so orienting at that edge yields exactly the form used in system (2). The modular argument then goes through. The stress-test note is right.

What is new: the k-restricted decomposition problem itself; Theorem 2's bound of sigma^{k+1}+4k+2 runs for the best decomposition, independent of |w|; and Theorem 3's unbounded worst/best ratio, proved by a self-contained construction of words whose eBWT has (ba)^n as its transform. The authors avoid the tempting route through Artin's conjecture and build the cycles directly. That is worth crediting.

Soft spots are minor. Theorem 2 needs the condition |w| >= k+1, since otherwise D_k(w) is empty; this is a small quantifier slip. The paper says "multiset" but actually counts ordered decompositions, which is what the concatenation order forces; the eBWT then ignores the order. That should be tidied but is not a mathematical error. No algorithm is given and NP-hardness is left open; the authors say this up front, so it is a stated limitation rather than a hidden flaw. Proposition 3's proof is a bit informal (the "sandwich" argument), but the 2|w| bound is correct.

Citation pattern looks honest: they credit the prior comparisons of BWT vs BBWT and explicitly flag that their result extends those to arbitrary k. The writing is clear for a specialist, and the proofs are checkable.

Verdict: this deserves a serious referee. I would accept it with minor revisions—fix the quantifier, tighten the multiset/sequence wording, and perhaps spell out the missing a->b-edge argument in Section 6. The paper gives the community a new problem and two non-obvious structural bounds, with a construction that does not lean on unproven number theory. I'd bring it to a reading group if anyone works on BWT variants; otherwise it's a nice one-idea paper.

Referee Report

0 major / 5 minor

Summary. The paper studies how the choice of a decomposition of a word into a multiset of strings affects the number of runs in the extended Burrows-Wheeler transform (eBWT) of that decomposition. It proves that the number of k-restricted decompositions of a length-n word grows exponentially (Theorem 1), that every word has a k-restricted decomposition whose eBWT has at most σ^{k+1}+4k+2 runs, independent of the word length (Theorem 2), and that there are words for which the ratio between the worst and best k-restricted decomposition is unbounded (Theorem 3). The proofs combine restricted-composition counting, a local perturbation bound for eBWT runs (Proposition 3), and a modular analysis of the eBWT antecedent of (ba)^n in Section 6.

Significance. If correct, these are the first results on the decomposition question for eBWT compression, and they establish that the optimization problem is both non-trivial and potentially very rewarding: good decompositions can be dramatically better than bad ones. The paper gives concrete proof ideas, including an explicit infinite family in Section 6, and it provides an online exploration tool. The main technical achievement, Theorem 3, relies on a clever use of the eBWT inverse to construct words whose forced decomposition has near-maximal runs while the best decomposition has constant runs; this should be of interest to the BWT and string-compression communities.

minor comments (5)

[Section 6, 'Subsequent values'] The classification of cycles as a_{i1} → x_{i2} → ... → b_{ik} → a_{i1} with t1=0 and tk=1 is stated without proof; the missing argument is that any mixed cycle must contain a b→a transition, so rotating the cycle to start at the target of that transition yields the stated form, while cycles consisting only of a's or only of b's are impossible because a-to-a transitions double the index (eventually forcing a b) and b-to-b transitions strictly decrease the index.
[Section 4 and Proposition 2] The notation C(n,k) is used both for the number of compositions with parts ≥ k and for the number of (k+1)-restricted compositions via |D_k(w)| = C(n,k+1); this overloading should be resolved for clarity, for instance by denoting the part size threshold explicitly.
[Theorem 2] Theorem 2 should state the hypothesis |w| ≥ k+1, since D_k(w) is empty for shorter words; the proof already implicitly assumes this because it constructs blocks of length k+1.
[Proposition 4] In the definition of w_q there is an off-by-one typo: the block should start at a_{(q-1)p+1} and run through a_{pq+r}, giving length p+r, rather than starting at a_{(q-1)p} as currently written.
[Section 4, proof of Theorem 1] The claim that the root r1 of maximum modulus is unique is not justified; this uniqueness is true for the polynomial X^c − X^{c−1} − 1, for instance via Perron-Frobenius theory on the companion matrix, but a short justification or citation would strengthen the asymptotic statement.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the derivation chain is self-contained and the Section 6 cycle-completeness concern is resolved by the a-to-b transition argument.

full rationale

The paper's three main results are proved from the definitions of BWT/eBWT and from standard external facts; I found no step in which a claimed prediction or derived quantity is equal, by construction, to an input or fitted parameter. Theorem 1 uses a standard stars-and-bars count and a cited formula for generalized Fibonacci numbers, with the asymptotic root bound supplied by Smyth's Mahler measure theorem; none of these inputs is the theorem itself. Theorem 2 constructs an explicit k-restricted decomposition into blocks of length k+1 and bounds its eBWT run count using Lemma 2 (rho(Sigma^p)=sigma^p), Corollary 3, and Proposition 3, all of which are derived from the eBWT definition rather than assumed from the target inequality. Theorem 3 follows from Theorem 2 and the Section 6 construction. The Section 6 construction uses only the bijectivity of the eBWT to define W(n) as the unique antecedent of (ba)^n and then uses modular arithmetic to force all inversion cycles to have length exceeding k. The reader-identified gap—that the linear system (2) might not characterize all short cycles—is not circular and in fact does not arise: any cycle containing only a's would require the index to double indefinitely and any cycle containing only b's would require the index to strictly decrease, so every cycle contains both letters and therefore contains an a-to-b edge; orienting the cycle at a b-to-a edge gives exactly the form a_{i1} -> ... -> b_{ik} -> a_{i1} with t_1=0 and t_k=1 used in the paper. The paper does not spell this out, but the omission is a presentational terseness, not a circular reduction. Appendix A is also non-circular: it explicitly notes that relying on Artin's conjecture would be unproved and instead the proof proceeds via the modular construction. There are no load-bearing self-citations, no fitted inputs renamed as predictions, and no results that reduce to their own assumptions. The work is self-contained against standard definitions and externally cited theorems, so the circularity score is 0.

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

No free parameters are fitted. The arguments rely on standard theorems and on the known bijective properties of the eBWT. No new entities are postulated.

assumptions (6)

standard math Standard eBWT properties: bijectivity, LF-mapping, and the rank correspondence between F and L columns (Proposition 1).
Used throughout; the inversion process in Section 6 relies on the rank correspondence between F and L columns.
standard math Harris & Styles identity for restricted compositions: sum of binomial coefficients equals a generalized Fibonacci number (from [14]).
Basis for Theorem 1's exponential count; identifies |D_k(w)| with a generalized Fibonacci number.
standard math Asymptotic form of generalized Fibonacci numbers with a dominant root (from [6,7]).
Used to state the exponential growth asymptotics in Theorem 1.
standard math Smyth's theorem on the Mahler measure of non-reciprocal polynomials (from [26]).
Used in Lemma 1 to guarantee a root of modulus >1 for X^c - X^{c-1} - 1.
standard math Circulant matrix inverse formula (proved in Appendix B).
Used in Section 6 to solve the linear system for cycle indices.
domain assumption Existence and uniqueness of the inverse eBWT for any multiset of strings (from [20]).
Section 6 defines W(n) as the unique multiset whose eBWT is (ba)^n.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Decomposing Words for Enhanced Compression: Exploring the Number of Runs in the Extended Burrows-Wheeler Transform." pith.science (2026). https://pith.science/paper/ADCRNBFS

@misc{pith2026250604926,
  author       = {Pith},
  title        = {Pith review of: Decomposing Words for Enhanced Compression: Exploring the Number of Runs in the Extended Burrows-Wheeler Transform},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ADCRNBFS}},
  note         = {Machine review of arXiv:2506.04926}
}

read the original abstract

The Burrows-Wheeler Transform (BWT) is a fundamental component in many data structures for text indexing and compression, widely used in areas such as bioinformatics and information retrieval. The extended BWT (eBWT) generalizes the classical BWT to multisets of strings, providing a flexible framework that captures many BWT-like constructions. Several known variants of the BWT can be viewed as instances of the eBWT applied to specific decompositions of a word. A central property of the BWT, essential for its compressibility, is the number of maximal ranges of equal letters, named runs. In this article, we explore how different decompositions of a word impact the number of runs in the resulting eBWT. First, we show that the number of decompositions of a word is exponential, even under minimal constraints on the size of the subsets in the decomposition. Second, we present an infinite family of words for which the ratio of the number of runs between the worst and best decompositions is unbounded, under the same minimal constraints. These results illustrate the potential cost of decomposition choices in eBWT-based compression and underline the challenges in optimizing run-length encoding in generalized BWT frameworks.

Figures

Figures reproduced from arXiv: 2506.04926 by the authors.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

27 extracted references · 22 canonical work pages

[1]

Sensitivity of string com- pressors and repetitiveness measures.Information and Computation, 291:104999, 2023

Tooru Akagi, Mitsuru Funakoshi, and Shunsuke Inenaga. Sensitivity of string com- pressors and repetitiveness measures.Information and Computation, 291:104999, 2023

work page 2023
[2]

Bijective BWT based com- pression schemes

Golnaz Badkobeh, Hideo Bannai, and Dominik Köppl. Bijective BWT based com- pression schemes. In Zsuzsanna Lipták, Edleno Silva de Moura, Karina Figueroa, and Ricardo Baeza-Yates, editors,String Processing and Information Retrieval - 31st International Symposium, SPIRE 2024, Puerto Vallarta, Mexico, September 23-25, 2024, Proceedings, volume 14899 of Lectu...

doi:10.1007/978-3-031-72200-4 2024
[3]

On the compressiveness of the Burrows-Wheeler transform

Hideo Bannai, Tomohiro I, and Yuto Nakashima. On the compres- siveness of the burrows-wheeler transform. CoRR, abs/2411.11298, 2024. URL: https://doi.org/10.48550/arXiv.2411.11298, arXiv:2411.11298, doi: 10.48550/ARXIV.2411.11298

work page Pith review arXiv doi:10.48550/arxiv.2411.11298 2024
[4]

Con- structing the bijective and the extended Burrows-Wheeler transform in linear time

Hideo Bannai, Juha Kärkkäinen, Dominik Köppl, and Marcin Piątkowski. Con- structing the bijective and the extended Burrows-Wheeler transform in linear time. In 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2021

work page 2021
[5]

On the number of equal-letter runs of the bijective burrows-wheeler transform.Theoretical Computer Science, 1027:115004, 2025

Elena Biagi, Davide Cenzato, Zsuzsanna Lipták, and Giuseppe Romana. On the number of equal-letter runs of the bijective burrows-wheeler transform.Theoretical Computer Science, 1027:115004, 2025

work page 2025
[6]

Classes of identities for the generalized Fibonacci numbers gn = gn−1 + gn−c from matrices with constant valued determinants.The Fibonacci Quarterly, 34(2):121–128, 1996

Marjorie Bicknell-Johnson and Colin Paul Spears. Classes of identities for the generalized Fibonacci numbers gn = gn−1 + gn−c from matrices with constant valued determinants.The Fibonacci Quarterly, 34(2):121–128, 1996

work page 1996
[7]

Linear recursion and Fibonacci sequences.(No Title), 1971

Alfred Brousseau. Linear recursion and Fibonacci sequences.(No Title), 1971

work page 1971
[8]

A block-sorting lossless data compression algorithm

Michael Burrows and David Wheeler. A block-sorting lossless data compression algorithm. SRS Research Report, 124, 1994

1994

Show all 27 references

[9]

A survey of bwt variants for string collec- tions

Davide Cenzato and Zsuzsanna Lipták. A survey of bwt variants for string collec- tions. Bioinformatics, 40(7):btae333, 2024

2024
[10]

Free differential calculus, iv

Kuo Tsai Chen, Ralph H Fox, and Roger C Lyndon. Free differential calculus, iv. the quotient groups of the lower central series.Annals of Mathematics, 68(1):81–95, 1958

1958
[11]

A bijective string sorting transform.arXiv preprint arXiv:1201.3077, 2012

Joseph Yossi Gil and David Allen Scott. A bijective string sorting transform.arXiv preprint arXiv:1201.3077, 2012

2012 arXiv
[12]

Novel results on the number of runs of the burrows- wheeler-transform

Sara Giuliani, Shunsuke Inenaga, Zsuzsanna Lipták, Nicola Prezza, Marinella Sciortino, and Anna Toffanello. Novel results on the number of runs of the burrows- wheeler-transform. In SOFSEM 2021: Theory and Practice of Computer Science: 47th International Conference on Current ...

2021
[13]

Novel results on the number of runs of the burrows- wheeler-transform

Sara Giuliani, Shunsuke Inenaga, Zsuzsanna Lipták, Nicola Prezza, Marinella Sciortino, and Anna Toffanello. Novel results on the number of runs of the burrows- wheeler-transform. In Tomás Bures, Riccardo Dondi, Johann Gamper, Giovanna Guerrini, Tomasz Jurdzinski, Claus Pahl, F...

2021
[14]

A generalization of the Fibonacci numbers.The Fibonacci Quarterly, 2(4):227–289, 1964

VC Harris and Carolyn C Styles. A generalization of the Fibonacci numbers.The Fibonacci Quarterly, 2(4):227–289, 1964

1964
[15]

Compositions ofn with parts in a set.Con- gressus Numerantium, 168:127, 2004

Silvia Heubach and Toufik Mansour. Compositions ofn with parts in a set.Con- gressus Numerantium, 168:127, 2004

2004
[16]

Closed form formula for the num- ber of restricted compositions

Gašper Jaklič, Vito Vitrih, and EMIL ŽAGAR. Closed form formula for the num- ber of restricted compositions. Bulletin of the Australian Mathematical Society, 81(2):289–297, 2010

2010
[17]

The sequence read archive: a decade more of explosive growth.Nucleic acids research, 50(D1):D387–D390, 2022

Kenneth Katz, Oleg Shutov, Richard Lapoint, Michael Kimelman, J Rodney Bris- ter, and Christopher O’Sullivan. The sequence read archive: a decade more of explosive growth.Nucleic acids research, 50(D1):D387–D390, 2022

2022
[18]

On circulant matrices.Notices of the AMS, 59(3):368–377, 2012

Irwin Kra and Santiago R Simanca. On circulant matrices.Notices of the AMS, 59(3):368–377, 2012

2012
[19]

Combinatorics on words, volume 17

Monsieur Lothaire. Combinatorics on words, volume 17. Cambridge university press, 1997

1997
[20]

An extension of the Burrows–Wheeler transform.Theoretical Computer Science, 387(3):298–312, 2007

Sabrina Mantaci, Antonio Restivo, Giovanna Rosone, and Marinella Sciortino. An extension of the Burrows–Wheeler transform.Theoretical Computer Science, 387(3):298–312, 2007

2007
[21]

Measuring the clustering effect of BWT via RLE.Theoretical Com- puter Science, 698:79–87, 2017

Sabrina Mantaci, Antonio Restivo, Giovanna Rosone, Marinella Sciortino, and Luca Versari. Measuring the clustering effect of BWT via RLE.Theoretical Com- puter Science, 698:79–87, 2017

2017
[22]

An analysis of the Burrows–Wheeler transform.Journal of the ACM (JACM), 48(3):407–430, 2001

Giovanni Manzini. An analysis of the Burrows–Wheeler transform.Journal of the ACM (JACM), 48(3):407–430, 2001

2001
[23]

Artin’s primitive root conjecture–a survey

Pieter Moree. Artin’s primitive root conjecture–a survey. Integers, 12(6):1305– 1416, 2012

2012
[24]

Indexing highly repetitive string collections

Gonzalo Navarro. Indexing highly repetitive string collections. arXiv preprint arXiv:2004.02781, 2020

2004 arXiv
[25]

Results of a prototype television bandwidth compression scheme

A Harry Robinson and Colin Cherry. Results of a prototype television bandwidth compression scheme. Proceedings of the IEEE, 55(3):356–364, 1967

1967
[26]

The Mahler measure of algebraic numbers: a survey.arXiv preprint math/0701397, 2007

Chris Smyth. The Mahler measure of algebraic numbers: a survey.arXiv preprint math/0701397, 2007. A When W (n) is reduced to a single string Theorem 4 would be straightforward if there were an infinite number of values of n such that |W (n)| = 1, since then we would haveminw∈W...

2025 arXiv
[2021]

doi:10.1007/978-3-030-67731-2\_18. 14 F. Ingels, A. Denis and B. Cazaux

doi

Pith tools

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

[1] [1]

Sensitivity of string com- pressors and repetitiveness measures.Information and Computation, 291:104999, 2023

Tooru Akagi, Mitsuru Funakoshi, and Shunsuke Inenaga. Sensitivity of string com- pressors and repetitiveness measures.Information and Computation, 291:104999, 2023

work page 2023

[2] [2]

Bijective BWT based com- pression schemes

Golnaz Badkobeh, Hideo Bannai, and Dominik Köppl. Bijective BWT based com- pression schemes. In Zsuzsanna Lipták, Edleno Silva de Moura, Karina Figueroa, and Ricardo Baeza-Yates, editors,String Processing and Information Retrieval - 31st International Symposium, SPIRE 2024, Puerto Vallarta, Mexico, September 23-25, 2024, Proceedings, volume 14899 of Lectu...

doi:10.1007/978-3-031-72200-4 2024

[3] [3]

On the compressiveness of the Burrows-Wheeler transform

Hideo Bannai, Tomohiro I, and Yuto Nakashima. On the compres- siveness of the burrows-wheeler transform. CoRR, abs/2411.11298, 2024. URL: https://doi.org/10.48550/arXiv.2411.11298, arXiv:2411.11298, doi: 10.48550/ARXIV.2411.11298

work page Pith review arXiv doi:10.48550/arxiv.2411.11298 2024

[4] [4]

Con- structing the bijective and the extended Burrows-Wheeler transform in linear time

Hideo Bannai, Juha Kärkkäinen, Dominik Köppl, and Marcin Piątkowski. Con- structing the bijective and the extended Burrows-Wheeler transform in linear time. In 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2021

work page 2021

[5] [5]

On the number of equal-letter runs of the bijective burrows-wheeler transform.Theoretical Computer Science, 1027:115004, 2025

Elena Biagi, Davide Cenzato, Zsuzsanna Lipták, and Giuseppe Romana. On the number of equal-letter runs of the bijective burrows-wheeler transform.Theoretical Computer Science, 1027:115004, 2025

work page 2025

[6] [6]

Classes of identities for the generalized Fibonacci numbers gn = gn−1 + gn−c from matrices with constant valued determinants.The Fibonacci Quarterly, 34(2):121–128, 1996

Marjorie Bicknell-Johnson and Colin Paul Spears. Classes of identities for the generalized Fibonacci numbers gn = gn−1 + gn−c from matrices with constant valued determinants.The Fibonacci Quarterly, 34(2):121–128, 1996

work page 1996

[7] [7]

Linear recursion and Fibonacci sequences.(No Title), 1971

Alfred Brousseau. Linear recursion and Fibonacci sequences.(No Title), 1971

work page 1971

[8] [8]

A block-sorting lossless data compression algorithm

Michael Burrows and David Wheeler. A block-sorting lossless data compression algorithm. SRS Research Report, 124, 1994

1994