Burrows–Wheeler transformations and de Bruijn words

We formulate and explain the extended BurrowsWheeler transform of Mantaci et al. from the viewpoint of permutations on a chain taken as a union of partial order-preserving mappings. In so doing we establish a link with syntactic semigroups of languages that are themselves cyclic semigroups. We apply the extended transform with a view to generating de Bruijn words through inverting the transform. We also make use of de Bruijn words to facilitate a proof that the maximum number of distinct factors of a word of length n has the form 12n2-O(nlogn). © 2012 Elsevier B.V. All rights reserved.