Research Repository

Burrows-Wheeler transformations and de Bruijn words

Higgins, PM (2012) 'Burrows-Wheeler transformations and de Bruijn words.' Theoretical Computer Science, 457. 128 - 136. ISSN 0304-3975

Full text not available from this repository.


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.

Item Type: Article
Subjects: Q Science > QA Mathematics
Divisions: Faculty of Science and Health > Mathematical Sciences, Department of
Depositing User: Jim Jamieson
Date Deposited: 12 Feb 2013 13:03
Last Modified: 23 Jan 2019 00:17

Actions (login required)

View Item View Item