106 citations · 239 across the 67 of their papers we have counts for
6 papers · 1 filter
On the compressiveness of the Burrows-Wheeler transform
Hideo Bannai, Tomohiro I, Yuto Nakashima
The Burrows-Wheeler transform (BWT) is a reversible transform that converts a string into another string . The size of the run-length encoded BWT (RLBWT) can b…
A Separation of and via Thue--Morse Words
Hideo Bannai, Mitsuru Funakoshi, Tomohiro I +3
We prove that for , the size of the smallest bidirectional scheme for the th Thue--Morse word is . Since Kutsukake et al. [SPIRE 2020] show that the…
Lyndon Words, the Three Squares Lemma, and Primitive Squares
Hideo Bannai, Takuya Mieno, Yuto Nakashima
We revisit the so-called "Three Squares Lemma" by Crochemore and Rytter [Algorithmica 1995] and, using arguments based on Lyndon words, derive a more general variant which consider…
Tight bounds on the maximum number of shortest unique substrings
Takuya Mieno, Shunsuke Inenaga, Hideo Bannai +1
A substring Q of a string S is called a shortest unique substring (SUS) for interval [s,t] in S, if Q occurs exactly once in S, this occurrence of Q contains interval [s,t], and ev…
The "Runs" Theorem
Hideo Bannai, Tomohiro I, Shunsuke Inenaga +3
We give a new characterization of maximal repetitions (or runs) in strings based on Lyndon words. The characterization leads to a proof of what was known as the "runs" conjecture (…
New Lower Bounds for the Maximum Number of Runs in a String
Kazuhiko Kusano, Wataru Matsubara, Akira Ishino +2
We show a new lower bound for the maximum number of runs in a string. We prove that for any e > 0, (a -- e)n is an asymptotic lower bound, where a = 56733/60064 = 0.944542. It is s…