String Covering: A Survey
From MaRDI portal
Abstract: The study of strings is an important combinatorial field that precedes the digital computer. Strings can be very long, trillions of letters, so it is important to find compact representations. Here we first survey various forms of one potential compaction methodology, the cover of a given string x, initially proposed in a simple form in 1990, but increasingly of interest as more sophisticated variants have been discovered. We then consider covering by a seed; that is, a cover of a superstring of x. We conclude with many proposals for research directions that could make significant contributions to string processing in future.
Recommendations
Cites work
- k-approximate quasiperiodicity under Hamming and edit distance
- A fast string searching algorithm
- A work-time optimal algorithm for computing all string covers
- ALGORITHMS FOR APPROXIMATE K-COVERING OF STRINGS
- Algorithms for computing the \(\lambda\)-regularities in strings
- Algorithms on Strings
- An on-line string superprimitivity test
- An optimal algorithm for computing the repetitions in a word
- An optimal algorithm to compute all the covers of a string
- An output-sensitive algorithm for the minimization of 2-dimensional string covers
- Approximate cover of strings
- Approximate periods of strings
- Approximate seeds of strings
- Can we recover the cover?
- Computing palindromic factorizations and palindromic covers on-line
- Computing regularities in strings: a survey
- Computing the \(\lambda \)-covers of a string
- Computing the cover array in linear time
- Computing the λ-Seeds of a String
- Cover array string reconstruction
- Covering a string
- Efficient algorithms for shortest partial seeds in words
- Efficient Computation of 2-Covers of a String.
- Efficient detection of quasiperiodicities in strings
- Efficient seed computation revisited
- Efficient seeds computation revisited
- Efficient string matching
- Enhanced covers of regular and indeterminate strings using prefix tables
- Enhanced string covering
- Experimental evaluation of algorithms for computing quasiperiods
- Fast algorithm for partial covers in words
- Fast Pattern Matching in Strings
- Finding the Anticover of a String
- Frequency covers for strings
- Generalized pattern matching and periodicity under substring consistent equivalence relations
- scientific article; zbMATH DE number 1615296 (Why is no real title available?)
- scientific article; zbMATH DE number 432779 (Why is no real title available?)
- scientific article; zbMATH DE number 3913711 (Why is no real title available?)
- scientific article; zbMATH DE number 3511563 (Why is no real title available?)
- scientific article; zbMATH DE number 2038766 (Why is no real title available?)
- scientific article; zbMATH DE number 2052918 (Why is no real title available?)
- scientific article; zbMATH DE number 1507240 (Why is no real title available?)
- scientific article; zbMATH DE number 1786458 (Why is no real title available?)
- scientific article; zbMATH DE number 7651109 (Why is no real title available?)
- scientific article; zbMATH DE number 7740932 (Why is no real title available?)
- scientific article; zbMATH DE number 7695998 (Why is no real title available?)
- Implementing approximate regularities
- Indexing weighted sequences: neat and efficient
- Inferring strings from cover arrays
- Linear work suffix array construction
- New complexity results for the k-covers problem
- On approximate enhanced covers under Hamming distance
- On left and right seeds of a string
- On the right-seed array of a string
- Optimal superprimitivity testing for strings
- Prefix table construction and conversion
- Quasi-Periodicity in Streams
- Quasi-periodicity under mismatch errors
- Repetitive perhaps, but certainly not boring
- Replacing suffix trees with enhanced suffix arrays
- Shortest covers of all cyclic shifts of a string
- Shortest covers of all cyclic shifts of a string
- String covering with optimal covers
- String covers of a tree
- Suffix Arrays: A New Method for On-Line String Searches
- The Complexity of Some Problems on Subsequences and Supersequences
- The complexity of the minimum k-cover problem
- The shortest common supersequence problem over binary alphabet is NP- complete
- The subtree max gap problem with application to parallel string covering
- The weighted suffix tree: an efficient data structure for handling molecular weighted sequences and its applications
- Truly Subquadratic-Time Extension Queries and Periodicity Detection in Strings with Uncertainties.
- Two strings at Hamming distance 1 cannot be both quasiperiodic
- Two-dimensional prefix string matching and covering on square matrices
- Uniqueness Theorems for Periodic Functions
- Universal reconstruction of a string
- Varieties of Regularities in Weighted Sequences
Cited in
(6)
This page was built for publication: String Covering: A Survey
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6145625)
