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