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.

Restivo, A., Rosone, G. (2009). Balanced Words Having Simple Burrows-Wheeler Transform. In Lecture Notes in Computer Science (pp.431-442) [10.1007/978-3-642-02737-6_35].

Balanced Words Having Simple Burrows-Wheeler Transform

RESTIVO, Antonio;ROSONE, Giovanna
2009-01-01

Abstract

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
Settore INF/01 - Informatica
2009
Developments in Language Theory, 13th International Conference, DLT 2009
Stuttgart, Germany
June 30 - July 3, 2009
2009
12
Restivo, A., Rosone, G. (2009). Balanced Words Having Simple Burrows-Wheeler Transform. In Lecture Notes in Computer Science (pp.431-442) [10.1007/978-3-642-02737-6_35].
Proceedings (atti dei congressi)
Restivo, A; Rosone, G
File in questo prodotto:
File Dimensione Formato  
RR_LNCS_DLT_2009.pdf

Solo gestori archvio

Dimensione 194.01 kB
Formato Adobe PDF
194.01 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10447/59403
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 6
  • ???jsp.display-item.citation.isi??? 4
social impact