An Extension of the String-to-String Correction Problem

DOI10.1145/321879.321880MaRDI QIDQ4055158zbMATH OpenOpenAlexWikidataFDO

Authors 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

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

Cited in

(40)

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

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

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