A lower bound for the edit-distance problem under an arbitrary cost function

DOI10.1016/0020-0190(88)90220-7MaRDI QIDQ1107330zbMATH OpenOpenAlexFDO

Authors Xiaoqiu Huang

Publication date 1988

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

Full work available at URL https://doi.org/10.1016/0020-0190(88)90220-7

zbMATH Keywords

lower boundedit distancelongest common subsequencesRAM model of computation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Discrete mathematics in relation to computer science (68R99)

Recommendations

• Classes of cost functions for string edit distance
• String editing under a combination of constraints
• scientific article; zbMATH DE number 3845091
• scientific article; zbMATH DE number 4053031
• Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)

Cites work

• A fast algorithm for computing longest common subsequences
• A faster algorithm computing string edit distances
• Algorithms for the Longest Common Subsequence Problem
• An information-theoretic lower bound for the longest common subsequence problem
• Bounds for the String Editing Problem
• Bounds on the Complexity of the Longest Common Subsequence Problem
• Improving the worst-case performance of the Hunt-Szymanski strategy for the longest common subsequence of two strings
• On the Optimality of Some Set Algorithms
• The String-to-String Correction Problem

Cited in

(7)

• Constrained string editing
• Lower bounding edit distances between permutations
• String editing under a combination of constraints
• Dynamic edit distance table under a general weighted cost function
• Classes of cost functions for string edit distance
• Bounds and estimates on the average edit distance
• Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)

This page was built for publication: A lower bound for the edit-distance problem under an arbitrary cost function

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