How hard is computing the edit distance?

DOI10.1006/inco.2000.2914zbMath1003.68054OpenAlexW1985354313WikidataQ61677533 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

Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (19)

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

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

This page was built for publication: How hard is computing the edit distance?