Suffix array and Lyndon factorization of a text

DOI10.1016/J.JDA.2014.06.001MaRDI QIDQ405567zbMATHOpenAlexFDO

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

Publication date 5 September 2014

Published in Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jda.2014.06.001

zbMATH Keywords

Lyndon wordsuffix arrayBWTLyndon factorizationsorting suffixes

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Recommendations

• Extended suffix array construction using Lyndon factors
• Suffixes, conjugates and Lyndon words
• Lyndon array construction during Burrows-Wheeler inversion
• Computing minimal and maximal suffixes of a substring revisited
• Lyndon factorization of grammar compressed texts revisited

Cites work

• scientific article; zbMATH DE number 432779 (Why is no real title available?)
• scientific article; zbMATH DE number 2183071 (Why is no real title available?)
• scientific article; zbMATH DE number 5499319 (Why is no real title available?)
• A constant-space comparison-based algorithm for computing the Burrows-Wheeler transform
• A quick tour on suffix arrays and compressed suffix arrays
• A space and time efficient algorithm for constructing compressed suffix arrays
• An extension of the Burrows-Wheeler transform
• Factorizing words over an ordered alphabet
• Fast parallel Lyndon factorization with applications
• Free differential calculus. IV: The quotient groups of the lower central series
• 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
• Lightweight data indexing and compression in external memory
• Lyndon words, permutations and trees.
• Parallel RAM algorithms for factorizing words
• Scalable Parallel Suffix Array Construction
• Suffixes, conjugates and Lyndon words
• Words over an ordered alphabet and suffix permutations

Cited in

(18)

• A combinatorial view on string attractors
• Inferring Strings from Lyndon Factorization
• Computation of the suffix array, Burrows-Wheeler transform and FM-index in \(V\)-order
• Can formal languages help pangenomics to represent and analyze multiple genomes?
• On arithmetically progressed suffix arrays and related Burrows-Wheeler transforms
• Cartesian and Lyndon trees
• A survey of string orderings and their application to the Burrows-Wheeler transform
• Lyndon words versus inverse Lyndon words: queries on suffixes and bordered words
• On the longest common prefix of suffixes in an inverse Lyndon factorization and other properties
• Constructing and indexing the bijective and extended Burrows-Wheeler transform
• Extended suffix array construction using Lyndon factors
• Inducing the Lyndon array
• Enhanced string factoring from alphabet orderings
• Suffixes, conjugates and Lyndon words
• \(V\)-order: new combinatorial properties \& a simple comparison algorithm
• Inverse Lyndon words and inverse Lyndon factorizations of words
• Lyndon factorization algorithms for small alphabets and run-length encoded strings
• Lyndon array construction during Burrows-Wheeler inversion

This page was built for publication: Suffix array and Lyndon factorization of a text

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