Universal reconstruction of a string

DOI10.1007/978-3-319-21840-3_32MaRDI QIDQ3449836zbMATH OpenOpenAlexFDO

Authors Paweł Gawrychowski, Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Tomasz Waleń

Publication date 30 October 2015

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-21840-3_32

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Recommendations

• Universal reconstruction of a string
• A linear algorithm for string reconstruction in the reverse complement equivalence model
• String reconstruction from substring compositions
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Reconstructing words from subwords in linear time

Cites work

• Algorithms on Strings
• Border array on bounded alphabet
• Cover array string reconstruction
• Efficient validation and construction of border arrays and validation of string matching automata
• scientific article; zbMATH DE number 3551946 (Why is no real title available?)
• scientific article; zbMATH DE number 1874382 (Why is no real title available?)
• Indeterminate strings, prefix arrays \& undirected graphs
• Inferring an indeterminate string from a prefix graph
• Inferring Strings from Lyndon Factorization
• Inferring strings from suffix trees and links on a binary alphabet
• Internal pattern matching queries in a text and applications
• Jewels of Stringology
• Linear time inference of strings from cover arrays using a binary alphabet (extended abstract)
• Linear work suffix array construction
• Mathematical Foundations of Computer Science 2003
• New bounds and extended relations between prefix arrays, border arrays, undirected graphs, and indeterminate strings
• Reverse engineering of compact suffix trees and links: a novel algorithm
• Reverse engineering prefix tables
• Reversing longest previous factor tables is hard
• Searching of Gapped Repeats and Subrepetitions in a Word
• The ``runs theorem
• Trans-dichotomous algorithms for minimum spanning trees and shortest paths
• Validating the Knuth-Morris-Pratt failure function, fast and online
• Verifying and enumerating parameterized border arrays

Cited in

(7)

• Lower bounds for the number of repetitions in 2D strings
• Universal reconstruction of a string
• Efficient Reconstruction of RC-Equivalent Strings
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• String reconstruction from substring compositions
• Tight bound for the number of distinct palindromes in a tree
• The problem of reconstructing a quasihomogeneous string from its part

This page was built for publication: Universal reconstruction of a string

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