Balanced Words Having Simple Burrows-Wheeler Transform

Risultato della ricerca: Other

4 Citazioni (Scopus)

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 <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.
Lingua originaleEnglish
Pagine431-442
Numero di pagine12
Stato di pubblicazionePublished - 2009

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • ???subjectarea.asjc.1700.1700???

Fingerprint Entra nei temi di ricerca di 'Balanced Words Having Simple Burrows-Wheeler Transform'. Insieme formano una fingerprint unica.

Cita questo