Bounds for the String Editing Problem

DOI10.1145/321921.321923zbMath0316.68019OpenAlexW2054882906MaRDI QIDQ4077436

No author found.

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

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

Related Items (21)

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

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