Tighter bounds for the sum of irreducible LCP values

DOI10.1016/J.TCS.2015.12.009MaRDI QIDQ507409zbMATHOpenAlexFDO

Authors Juha Kärkkäinen, Dominik Kempa, Marcin Piatkowski

Publication date 6 February 2017

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

Full work available at URL https://doi.org/10.1016/j.tcs.2015.12.009

zbMATH Keywords

LCP arraysuffix arrayBurrows-Wheeler transformirreducible LCP values

Mathematics Subject Classification ID

Information storage and retrieval of data (68P20) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Combinatorics on words (68R15)

Recommendations

• Tighter bounds for the sum of irreducible LCP values
• Algorithm Theory - SWAT 2004
• scientific article; zbMATH DE number 2119665
• Wee LCP
• Burrows-Wheeler transform and LCP array construction in constant space

Cites work

• scientific article; zbMATH DE number 1052006 (Why is no real title available?)
• Algorithm Theory - SWAT 2004
• An extension of the Burrows-Wheeler transform
• Bioinformatics algorithms. Sequence analysis, genome rearrangements, and phylogenetic reconstruction
• Burrows-Wheeler transformations and de Bruijn words
• Compressed representations of sequences and full-text indexes
• Compressed suffix trees, efficient computation and storage of LCP-values
• Computing the Burrows-Wheeler transform of a string and its reverse in parallel
• Fixed point theorems for the generalized \(\Psi\)-set contraction mapping on an abstract convex space
• Permuted Longest-Common-Prefix Array
• Replacing suffix trees with enhanced suffix arrays
• Sampled Longest Common Prefix Array
• Suffix Arrays: A New Method for On-Line String Searches
• Uniqueness Theorems for Periodic Functions

Cited in

(3)

• On suffix tree breadth
• Tight upper and lower bounds on suffix tree breadth
• Tighter bounds for the sum of irreducible LCP values

This page was built for publication: Tighter bounds for the sum of irreducible LCP values

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