Inferring strings from suffix trees and links on a binary alphabet

DOI10.1016/J.DAM.2013.02.033MaRDI QIDQ496548zbMATHOpenAlexFDO

Authors Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Tomohiro I

Publication date 22 September 2015

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2013.02.033

zbMATH Keywords

suffix treesenumeration problemreverse engineering problem

Mathematics Subject Classification ID

Data structures (68P05) Algorithms on strings (68W32)

Recommendations

• Reverse engineering of compact suffix trees and links: a novel algorithm
• scientific article; zbMATH DE number 2052919
• Space efficient suffix trees

Cites work

• scientific article; zbMATH DE number 3913711 (Why is no real title available?)
• scientific article; zbMATH DE number 177570 (Why is no real title available?)
• scientific article; zbMATH DE number 1874382 (Why is no real title available?)
• A Space-Economical Suffix Tree Construction Algorithm
• Algorithms on Strings, Trees and Sequences
• Border array on bounded alphabet
• Counting Parameterized Border Arrays for a Binary Alphabet
• Counting distinct strings
• Counting suffix arrays and strings
• Cover array string reconstruction
• Efficient validation and construction of border arrays and validation of string matching automata
• Mathematical Foundations of Computer Science 2003
• On-line construction of suffix trees
• Reverse engineering prefix tables
• Validating the Knuth-Morris-Pratt failure function, fast and online
• Verifying a parameterized border array in \(O(n ^{1.5})\) time
• Words over an ordered alphabet and suffix permutations

Cited in

(14)

• Recognizing union-find trees is NP-complete, even without rank info
• On the size of the smallest alphabet for Lyndon trees
• Inferring strings from position heaps in linear time
• Recognizing union-find trees is NP-complete
• On suffix tree detection
• From Suffix Trees to Suffix Vectors
• On suffix tree detection
• Reverse engineering of compact suffix trees and links: a novel algorithm
• String inference from longest-common-prefix array
• When a dollar makes a BWT
• Universal reconstruction of a string
• Universal reconstruction of a string
• Inferring strings from Lyndon factorization
• Verifying and enumerating parameterized border arrays

This page was built for publication: Inferring strings from suffix trees and links on a binary alphabet

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