How hard is computing the edit distance?
type: Item
instance of: scholarly article
title: How hard is computing the edit distance?
zbMATH Open document ID: 1003.68054
author: Giovanni Pighizzini
published in: Information and Computation
publication date: 2003-01-14T00:00:00Z
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 1853156
MaRDI profile type: Publication
full work available at URL: inco.2000.2914
OpenAlex ID: W1985354313
Wikidata QID: Q61677533
cites work: A Minimum Distance Error-Correcting Parser for Context-Free Languages
cites work: The complexity of computing maximal word functions
cites work: Depth reduction for noncommutative arithmetic circuits
cites work: Non-commutative arithmetic circuits: depth reduction and size lower bounds
cites work: The longest common subsequence problem revisited
cites work: Q4131653
cites work: Alternation
cites work: Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
cites work: A taxonomy of problems with fast parallel algorithms
cites work: Q4206397
cites work: Q3862379
cites work: The complexity of ranking simple languages
cites work: Effective entropies and data compression
cites work: Q4142699
cites work: Mapping the genome
cites work: Q5528329
cites work: Syntax-directed least-errors analysis for context-free languages
cites work: Efficient Parallel Evaluation of Straight-Line Code and Arithmetic Circuits
cites work: Spelling correction in systems programs
cites work: A Method for the Correction of Garbled Words Based on the Levenshtein Metric
cites work: Finding the maximum, merging, and sorting in a parallel computation model
cites work: Near-optimal, single-synchronization-error-correcting code
cites work: Order- n correction for regular languages
cites work: The String-to-String Correction Problem
DBLP publication ID: journals/iandc/Pighizzini01
DOI: 10.1006/INCO.2000.2914
description: scientific article; zbMATH DE number 1853156