Computing Inverse ST in Linear Complexity

DOI10.1007/978-3-540-69068-9_18MaRDI QIDQ3506952zbMATH OpenOpenAlexFDO

Authors Ge Nong, Sen Zhang, W. H. Chan

Publication date 17 June 2008

Published in Combinatorial Pattern Matching (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-69068-9_18

Mathematics Subject Classification ID

Searching and sorting (68P10) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05)

Recommendations

• Computing the inverse sort transform in linear time
• Linear complexity inversion algorithms for a class of structured matrices
• Rigorous Time/Space Trade-offs for Inverting Functions
• On the complexity of inverting integer and polynomial matrices
• scientific article; zbMATH DE number 1962830
• Complexity of inverting the Euler function
• scientific article; zbMATH DE number 1205991
• scientific article; zbMATH DE number 1543035
• Polynomial-time inverse computation for accumulative functions with multiple data traversals
• Structural analysis of the complexity of inverse functions

Cited in

(3)

• \(xkcd\)-repeats: a new taxonomy of repeats defined by their context diversity
• Computing the inverse sort transform in linear time
• Complexity of inverting the Euler function

This page was built for publication: Computing Inverse ST in Linear Complexity

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