Bounds for the String Editing Problem

DOI10.1145/321921.321923MaRDI QIDQ4077436zbMATH OpenOpenAlexFDO

Authors

Publication date 1976

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

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

Mathematics Subject Classification ID

General topics in the theory of software (68N01) Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Algorithms in computer science (68W99)

Cited in

(22)

• An overview on XML similarity: background, current trends and future directions
• Constrained string editing
• APPLICATION-SPECIFIC ARRAY PROCESSORS FOR THE LONGEST COMMON SUBSEQUENCE PROBLEM OF THREE SEQUENCES ∗ †
• A lower bound for the edit-distance problem under an arbitrary cost function
• Optimal parallel detection of squares in strings
• Fast approximate dictionary matching
• A new practical linear space algorithm for the longest common subsequence problem
• Longest common subsequences
• The tree-to-tree editing problem
• Dynamic programming with convexity, concavity and sparsity
• New tabulation and sparse dynamic programming based techniques for sequence similarity problems
• A faster algorithm computing string edit distances
• A common basis for similarity measures involving two strings†
• New algorithms for the LCS problem
• A bit-string longest-common-subsequence algorithm
• On the inadequacy of tournament algorithms for the N-SCS problem
• Computing a longest common subsequence for a set of strings
• A fast algorithm for the longest-common-subsequence problem
• The string merging problem
• Efficient CRCW-PRAM algorithms for universal substring searching
• Automatic error correction in flexion languages
• Sequence matching with binary codes

This page was built for publication: Bounds for the String Editing Problem

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