TY - CONF
T1 - Balanced Words Having Simple Burrows-Wheeler Transform
AU - Restivo, Antonio
AU - Rosone, Giovanna
PY - 2009
Y1 - 2009
N2 - The investigation of the "clustering effect" of the Burrows-Wheeler transform (BWT) leads to study the words having simple BWT , i.e. 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_1^{n_1}$, for some non-negative integers $n_1, n_2, \ldots, n_k$.We remark that, in the case of binary alphabets, there is an equivalence between words having simple BWT, the family of (circular) balanced words and the conjugates of standard words. In the case of alphabets of size greater than two, there is no more equivalence between these notions. As a main result of this paper we prove that, under assumption of balancing, the following three conditions on a word w are equivalent: i) w has simple BWT, ii) w is a circularly rich word, and iii) w is a conjugate of a finite epistandard word.
AB - The investigation of the "clustering effect" of the Burrows-Wheeler transform (BWT) leads to study the words having simple BWT , i.e. 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_1^{n_1}$, for some non-negative integers $n_1, n_2, \ldots, n_k$.We remark that, in the case of binary alphabets, there is an equivalence between words having simple BWT, the family of (circular) balanced words and the conjugates of standard words. In the case of alphabets of size greater than two, there is no more equivalence between these notions. As a main result of this paper we prove that, under assumption of balancing, the following three conditions on a word w are equivalent: i) w has simple BWT, ii) w is a circularly rich word, and iii) w is a conjugate of a finite epistandard word.
KW - Balanced sequences
KW - Burrows Wheeler Transform
KW - Combinatorics on Words
KW - epistandard
KW - rich words
KW - words having simple BWT
KW - Balanced sequences
KW - Burrows Wheeler Transform
KW - Combinatorics on Words
KW - epistandard
KW - rich words
KW - words having simple BWT
UR - http://hdl.handle.net/10447/59403
M3 - Other
SP - 431
EP - 442
ER -