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.Abstract
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 |
URI: | http://repository.essex.ac.uk/id/eprint/5515 |
Actions (login required)
![]() |
View Item |