On a cyclic string-to-string correction problem

DOI10.1016/0020-0190(90)90109-BzbMath0697.68044OpenAlexW2021202955MaRDI QIDQ911767

Maurice Maes

Publication date: 1990

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(90)90109-b

zbMATH Keywords

analysis of algorithmspattern matchingcyclic stringsstring-to-string correction problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (22)

Circular Sequence Comparison with q-grams ⋮ A fast algorithm for stereo matching ⋮ On hidden Markov models and cyclic strings for shape recognition ⋮ Longest common subsequence problem for unoriented and cyclic strings ⋮ An improved algorithm for solving the banded cyclic string-to-string correction problem ⋮ Accurate and Efficient Methods to Improve Multiple Circular Sequence Alignment ⋮ Efficient merged longest common subsequence algorithms for similar sequences ⋮ Linear-space S-table algorithms for the longest common subsequence problem ⋮ Monge properties of sequence alignment ⋮ Alignments of mitochondrial genome arrangements: applications to metazoan phylogeny ⋮ APPROXIMATION ALGORITHMS FOR LOCAL ALIGNMENT WITH LENGTH CONSTRAINTS ⋮ An all-substrings common subsequence algorithm ⋮ Tandem cyclic alignment ⋮ Crossing numbers of graphs with rotation systems ⋮ FINDING MANY OPTIMAL PATHS WITHOUT GROWING ANY OPTIMAL PATH TREES ⋮ Alignment-free sequence comparison using absent words ⋮ Crossing Number of Graphs with Rotation Systems ⋮ Computational geometric aspects of rhythm, melody, and voice-leading ⋮ Approximate labelled subtree homeomorphism ⋮ Alignments with non-overlapping moves, inversions and tandem duplications in \(O(n^{4})\) time ⋮ Unnamed Item ⋮ Tree edit distance with gaps

Cites Work

• Optimal matching of deformed patterns with positional influence
• A linear space algorithm for computing maximal common subsequences
• Stochastic Error-Correcting Syntax Analysis for Recognition of Noisy Patterns
• The String-to-String Correction Problem

This page was built for publication: On a cyclic string-to-string correction problem