Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
427141 | Information Processing Letters | 2013 | 6 Pages |
•A new bijective combinatorial characterization of suffix array permutations is obtained.•An existing characterization of Burrows–Wheeler transform can be advantageously applied to suffix arrays.•A known suffix array characterization for binary alphabet is easily obtained through our approach.•Known counting results can be obtained more simply with our characterization.
We present a bijective characterization of suffix array permutations obtained from a characterization of Burrows–Wheeler arrays given in [1]. We show that previous characterizations [2], [3] and [4], or their analogs, can be obtained in a simple and elegant way using this relationship. To demonstrate the usefulness of our approach, we obtain simpler proofs for some known enumeration results about suffix arrays [3]. Our characterization of suffix arrays is the first based on their relationship with Burrows–Wheeler permutations.