An Extension of the String-to-String Correction Problem

DOI10.1145/321879.321880zbMath0301.68028OpenAlexW2039262760WikidataQ63443912 ScholiaQ63443912MaRDI QIDQ4055158

Roy Lowrance, Robert A. Wagner

Publication date: 1975

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/321879.321880

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) General topics in the theory of software (68N01)

Related Items (39)

The principle of optimality in the design of efficient algorithms ⋮ Swap and mismatch edit distance ⋮ Efficient special cases of pattern matching with swaps ⋮ Fast approximate matching of words against a dictionary ⋮ Exploiting pseudo-locality of interchange distance ⋮ Probabilistic models of genome shuffling ⋮ The approximate swap and mismatch edit distance ⋮ On the hardness of the consensus string problem ⋮ Adaptive Computation of the Swap-Insert Correction Distance ⋮ A faster algorithm computing string edit distances ⋮ Approximate String Matching with Address Bit Errors ⋮ Overlap matching. ⋮ The string merging problem ⋮ Extending alignments with \(k\)-mismatches and \(\ell\)-gaps ⋮ String matching with up to \(k\) swaps and mismatches ⋮ Charge and reduce: A fixed-parameter algorithm for string-to-string correction ⋮ A Simple Algorithm for Approximating the Text-To-Pattern Hamming Distance ⋮ Pattern matching with address errors: rearrangement distances ⋮ Using swaps and deletes to make strings match ⋮ Property matching and weighted matching ⋮ Pattern matching with pair correlation distance ⋮ Function approximation on non-Euclidean spaces ⋮ Finite automata based algorithms on subsequences and supersequences of degenerate strings ⋮ Crossing numbers of graphs with rotation systems ⋮ Approximate string matching with stuck address bits ⋮ Unnamed Item ⋮ Polynomial-time equivalences and refined algorithms for longest common subsequence variants ⋮ Crossing Number of Graphs with Rotation Systems ⋮ Efficient computations of \(\ell _1\) and \(\ell _{\infty }\) rearrangement distances ⋮ Optimal and information theoretic syntactic pattern recognition involving traditional and transposition errors ⋮ Reconstructing a history of recombinations from a set of sequences ⋮ Approximate string matching with address bit errors ⋮ Efficient algorithms for approximate string matching with swaps ⋮ Computing a longest common subsequence for a set of strings ⋮ Properties of Levenshtein metrics on sequences ⋮ Approximate swapped matching. ⋮ Automatic error correction in flexion languages ⋮ A model and a fast algorithm for multiple errors spelling correction ⋮ New algorithms for the LCS problem

This page was built for publication: An Extension of the String-to-String Correction Problem