A lower bound for the edit-distance problem under an arbitrary cost function
type: Item
instance of: scholarly article
title: A lower bound for the edit-distance problem under an arbitrary cost function
zbMATH Open document ID: 0652.68090
DOI: 10.1016/0020-0190(88)90220-7
author: Xiaoqiu Huang
published in: Information Processing Letters
publication date: 1988-01-01T00:00:00Z
Mathematics Subject Classification ID: 68R99
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 4064521
zbMATH Keywords: lower bound
zbMATH Keywords: edit distance
zbMATH Keywords: RAM model of computation
zbMATH Keywords: longest common subsequences
MaRDI profile type: Publication
full work available at URL: 0020-0190(88)90220-7
OpenAlex ID: W1986124289
cites work: Bounds on the Complexity of the Longest Common Subsequence Problem
cites work: Improving the worst-case performance of the Hunt-Szymanski strategy for the longest common subsequence of two strings
cites work: Algorithms for the Longest Common Subsequence Problem
cites work: An information-theoretic lower bound for the longest common subsequence problem
cites work: A fast algorithm for computing longest common subsequences
cites work: A faster algorithm computing string edit distances
cites work: On the Optimality of Some Set Algorithms
cites work: The String-to-String Correction Problem
cites work: Bounds for the String Editing Problem
description: scientific article; zbMATH DE number 4064521