Approximate periods of strings

DOI10.1016/S0304-3975(00)00365-0MaRDI QIDQ5958136zbMATH OpenFDO

Authors J. S. Sim, Costas S. Iliopoulos, Kunsoo Park, W. F. Smyth

Publication date 3 March 2002

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

Full work available at URL https://doi.org/10.1016/S0304-3975(00)00365-0

zbMATH Keywords

approximate periodsdistance functionperiodicityrepetitions

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorics on words (68R15) Algorithms on strings (68W32)

Recommendations

• scientific article; zbMATH DE number 2185637
• Approximate Periodicity
• Algorithms For Computing Approximate Repetitions In Musical Sequences
• scientific article; zbMATH DE number 1092948
• Implementing approximate regularities

Cites work

• A work-time optimal algorithm for computing all string covers
• All Highest Scoring Paths in Weighted Grid Graphs and Their Application to Finding All Approximate Repeats in Strings
• An O(n log n) algorithm for finding all repetitions in a string
• An on-line string superprimitivity test
• An Optimal O(\log \log N)-Time Parallel Algorithm for Detecting all Squares in a String
• An optimal algorithm for computing the repetitions in a word
• Covering a string
• Efficient detection of quasiperiodicities in strings
• Fast Pattern Matching in Strings
• scientific article; zbMATH DE number 1615270 (Why is no real title available?)
• scientific article; zbMATH DE number 1507240 (Why is no real title available?)
• scientific article; zbMATH DE number 801745 (Why is no real title available?)
• Incremental String Comparison
• More on the complexity of common superstring and supersequence problems
• Optimal off-line detection of repetitions in a string
• Optimal parallel algorithms for periods, palindromes and squares (extended abstract)
• Optimal superprimitivity testing for strings
• Pattern recognition in genetic sequences by mismatch density
• Testing string superprimitivity in parallel
• The Complexity of Some Problems on Subsequences and Supersequences
• The shortest common supersequence problem over binary alphabet is NP- complete
• The subtree max gap problem with application to parallel string covering
• Two-dimensional prefix string matching and covering on square matrices

Cited in

(18)

• The approximate period problem for DNA alphabet.
• Period recovery of strings over the Hamming and edit distances
• k-approximate quasiperiodicity under Hamming and edit distance
• Multidimensional period recovery
• Approximate cover of strings
• Approximate periodicity
• Can we recover the cover?
• scientific article; zbMATH DE number 2185637 (Why is no real title available?)
• String Periods in the Order-Preserving Model
• Approximate Periods with Levenshtein Distance
• scientific article; zbMATH DE number 1092948 (Why is no real title available?)
• Algorithms For Computing Approximate Repetitions In Musical Sequences
• Quasi-periodicity under mismatch errors
• Generalized approximate regularities in strings
• ALGORITHMS FOR APPROXIMATE K-COVERING OF STRINGS
• String Covering: A Survey
• Implementing approximate regularities
• A dynamic edit distance table

This page was built for publication: Approximate periods of strings

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