  The Burrows-Wheeler Transform (BWT) is a word transformation introduced in
1994 for Data Compression. It has become a fundamental tool for designing
self-indexing data structures, with important applications in several area in
science and engineering. The Alternating Burrows-Wheeler Transform (ABWT) is
another transformation recently introduced in [Gessel et al. 2012] and studied
in the field of Combinatorics on Words. It is analogous to the BWT, except that
it uses an alternating lexicographical order instead of the usual one. Building
on results in [Giancarlo et al. 2018], where we have shown that BWT and ABWT
are part of a larger class of reversible transformations, here we provide a
combinatorial and algorithmic study of the novel transform ABWT. We establish a
deep analogy between BWT and ABWT by proving they are the only ones in the
above mentioned class to be rank-invertible, a novel notion guaranteeing
efficient invertibility. In addition, we show that the backward-search
procedure can be efficiently generalized to the ABWT; this result implies that
also the ABWT can be used as a basis for efficient compressed full text
indices. Finally, we prove that the ABWT can be efficiently computed by using a
combination of the Difference Cover suffix sorting algorithm
[K\"{a}rkk\"{a}inen et al., 2006] with a linear time algorithm for finding the
minimal cyclic rotation of a word with respect to the alternating
lexicographical order.
