Burrows-Wheeler transformations and de Bruijn words

DOI10.1016/J.TCS.2012.07.019MaRDI QIDQ714849zbMATH OpenOpenAlexFDO

Authors Peter M. Higgins

Publication date 11 October 2012

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1901.08392

zbMATH Keywords

Lyndon wordBurros-Wheeler transformde Bruijn wordGessel-Reutenauer bijection

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Combinatorics on words (68R15)

Abstract: We formulate and explain the extended Burrows-Wheeler 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.

Recommendations

• scientific article; zbMATH DE number 2051173
• An extension of the Burrows-Wheeler transform
• From first principles to the Burrows and Wheeler transform and beyond, via combinatorial optimization
• The Burrows-Wheeler transform between data compression and combinatorics on words
• Words with simple Burrows-Wheeler transforms

Cites work

• scientific article; zbMATH DE number 4028925 (Why is no real title available?)
• scientific article; zbMATH DE number 1737190 (Why is no real title available?)
• scientific article; zbMATH DE number 3068971 (Why is no real title available?)
• A note on the Burrows-Wheeler transformation
• An extension of the Burrows-Wheeler transform
• Combinatorial Pattern Matching
• Counting permutations with given cycle structure and descent set
• Necklaces of beads in k colors and k-ary de Bruijn sequences
• On the theorem of Fredricksen and Maiorana about de Bruijn sequences
• THE SEMIGROUP OF CONJUGATES OF A WORD

Cited in

(15)

• A BWT-based algorithm for random de Bruijn sequence construction
• Words with simple Burrows-Wheeler transforms
• A bijection between words and multisets of necklaces
• String inference from longest-common-prefix array
• Tighter bounds for the sum of irreducible LCP values
• Measuring the clustering effect of BWT via RLE
• Burrows-Wheeler transform and run-length enconding
• Sorting conjugates and suffixes of words in a multiset
• Tighter bounds for the sum of irreducible LCP values
• scientific article; zbMATH DE number 2051173 (Why is no real title available?)
• FUNCTIONAL PEARL Inverting the Burrows–Wheeler transform
• Regular Transformations of Data Words Through Origin Information
• Computing the Burrows-Wheeler Transform of a String and Its Reverse
• On semi-perfect de Bruijn words
• An extension of the Burrows-Wheeler transform

This page was built for publication: Burrows-Wheeler transformations and de Bruijn words

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q714849)