How hard is computing the edit distance?

DOI10.1006/inco.2000.2914zbMath1003.68054WikidataQ61677533 ScholiaQ61677533MaRDI QIDQ1854409

Giovanni Pighizzini

Publication date: 14 January 2003

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/inco.2000.2914

Mathematics Subject Classification ID

68Q45: Formal languages and automata

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Related Items

Quasi-Distances and Weighted Finite Automata, THE EDIT-DISTANCE BETWEEN A REGULAR LANGUAGE AND A CONTEXT-FREE LANGUAGE, Consensus String Problem for Multiple Regular Languages, Edit distance neighbourhoods of input-driven pushdown automata, The intractability of computing the Hamming distance, A simple attack on some clock-controlled generators, Computing the edit distance of a regular language, Prefix Distance Between Regular Languages, STATE COMPLEXITY OF ADDITIVE WEIGHTED FINITE AUTOMATA, String distances and intrusion detection: Bridging the gap between formal languages and computer security, Edit Distance for Pushdown Automata, State Complexity of Neighbourhoods and Approximate Pattern Matching

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Effective entropies and data compression
• The longest common subsequence problem revisited
• Non-commutative arithmetic circuits: depth reduction and size lower bounds
• The complexity of computing maximal word functions
• The complexity of ranking simple languages
• A taxonomy of problems with fast parallel algorithms
• Efficient Parallel Evaluation of Straight-Line Code and Arithmetic Circuits
• Finding the maximum, merging, and sorting in a parallel computation model
• Alternation
• A Method for the Correction of Garbled Words Based on the Levenshtein Metric
• Order- n correction for regular languages
• The String-to-String Correction Problem
• Syntax-directed least-errors analysis for context-free languages
• Mapping the genome
• Depth reduction for noncommutative arithmetic circuits
• Near-optimal, single-synchronization-error-correcting code
• Spelling correction in systems programs
• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
• A Minimum Distance Error-Correcting Parser for Context-Free Languages