Sorting conjugates and suffixes of words in a multiset

DOI10.1142/S0129054114400309MaRDI QIDQ5247182zbMATH OpenFDO

Authors Silvia Bonomo, Giovanna Rosone, M. Sciortino, Sabrina Mantaci, Antonio Restivo

Publication date 23 April 2015

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/S0129054114400309

zbMATH Keywords

Burrows-Wheeler transformcircular wordsconjugatesextended Burrows-Wheeler transformLyndon wordssortingsuffixes

Mathematics Subject Classification ID

Searching and sorting (68P10) Combinatorics on words (68R15) Algorithms on strings (68W32) Protein sequences, DNA sequences (92D20)

Recommendations

• Suffixes, conjugates and Lyndon words
• A survey of string orderings and their application to the Burrows-Wheeler transform
• An extension of the Burrows-Wheeler transform
• Combinatorial Pattern Matching
• Burrows-Wheeler transformations and de Bruijn words

Cites work

• A new combinatorial approach to sequence comparison
• A note on the Burrows-Wheeler transformation
• An extension of the Burrows-Wheeler transform
• Counting permutations with given cycle structure and descent set
• Factorizing words over an ordered alphabet
• From first principles to the Burrows and Wheeler transform and beyond, via combinatorial optimization
• Lightweight algorithms for constructing and inverting the BWT of string collections

Cited in

(14)

• A combinatorial view on string attractors
• When a dollar makes a BWT
• Lightweight merging of compressed indices based on BWT variants
• The alternating BWT: an algorithmic perspective
• On generalized Lyndon words
• scientific article; zbMATH DE number 3963207 (Why is no real title available?)
• Some variations on Lyndon words (invited talk)
• Indexing the bijective BWT
• Suffixes, conjugates and Lyndon words
• Constructing and indexing the bijective and extended Burrows-Wheeler transform
• Sorting circular suffixes in linear time
• Generic non-recursive suffix array construction
• Improved circular dictionary matching
• Fast and memory-efficient bwt construction of repetitive texts using Lyndon grammars

This page was built for publication: Sorting conjugates and suffixes of words in a multiset

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