DOIAbstract
The investigation of the extremal case of the Burrows-Wheeler transform leads to study the words $w$ over an ordered alphabet $A=\{a_1,a_2,\ldots,a_k\}$, with $a_1 < a_2 < \ldots <a_k$, such that $bwt(w)$ is of the form $a_k^{n_k} a_{k-1}^{n_{k-1}} \cdots a_2^{n_2}a_1^{n_1}$, for some non-negative integers $n_1, n_2, \ldots, n_k$. A characterization of these words in the case $|A|=2$ has been given in~\cite{MaReSc}, where it is proved that they correspond to the powers of conjugates of standard words. The case $|A|=3$ has been settled in [Jamie Simpson, Simon J. Puglisi, Words with simple Burrows-Wheeler transforms, Electronic Journal of Combinatorics 15, (2008) article R83], which also contains some partial results for an arbitrary alphabe...
Add to ORKG