How hard is computing the edit distance?
From MaRDI portal
Publication:1854409
DOI10.1006/inco.2000.2914zbMath1003.68054WikidataQ61677533 ScholiaQ61677533MaRDI QIDQ1854409
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
68Q45: Formal languages and automata
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
The intractability of computing the Hamming distance, A simple attack on some clock-controlled generators, Computing the edit distance of a regular language, STATE COMPLEXITY OF ADDITIVE WEIGHTED FINITE AUTOMATA, 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
