How hard is computing the edit distance?
From MaRDI portal
Recommendations
Cites work
- scientific article; zbMATH DE number 3664335 (Why is no real title available?)
- scientific article; zbMATH DE number 3560742 (Why is no real title available?)
- scientific article; zbMATH DE number 3571502 (Why is no real title available?)
- scientific article; zbMATH DE number 4126696 (Why is no real title available?)
- scientific article; zbMATH DE number 3240929 (Why is no real title available?)
- A Method for the Correction of Garbled Words Based on the Levenshtein Metric
- A Minimum Distance Error-Correcting Parser for Context-Free Languages
- A taxonomy of problems with fast parallel algorithms
- Alternation
- Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
- Depth reduction for noncommutative arithmetic circuits
- Effective entropies and data compression
- Efficient Parallel Evaluation of Straight-Line Code and Arithmetic Circuits
- Finding the maximum, merging, and sorting in a parallel computation model
- Mapping the genome
- Near-optimal, single-synchronization-error-correcting code
- Non-commutative arithmetic circuits: depth reduction and size lower bounds
- Order- n correction for regular languages
- Spelling correction in systems programs
- Syntax-directed least-errors analysis for context-free languages
- The String-to-String Correction Problem
- The complexity of computing maximal word functions
- The complexity of ranking simple languages
- The longest common subsequence problem revisited
Cited in
(31)- Quasi-distances and weighted finite automata
- Consensus string problem for multiple regular languages
- scientific article; zbMATH DE number 1962763 (Why is no real title available?)
- Descriptional complexity of error detection
- EDIT-DISTANCE OF WEIGHTED AUTOMATA: GENERAL DEFINITIONS AND ALGORITHMS
- A simple attack on some clock-controlled generators
- Edit distance neighbourhoods of input-driven pushdown automata
- Input-driven pushdown automata for edit distance neighborhood
- scientific article; zbMATH DE number 4053031 (Why is no real title available?)
- An error correcting parser for context free grammars that takes less than cubic time
- The intractability of computing the Hamming distance
- Edit distance neighbourhoods of input-driven pushdown automata
- Edit distance for pushdown automata
- The edit-distance between a regular language and a context-free language
- State complexity of additive weighted finite automata
- Computing the expected edit distance from a string to a PFA
- State complexity of neighbourhoods and approximate pattern matching
- Consensus string problem for multiple regular languages
- Absent Subsequences in Words
- Computing the edit distance of a regular language
- Edit distance for pushdown automata
- Computing the Shortest String and the Edit-Distance for Parsing Expression Languages
- State complexity of neighbourhoods and approximate pattern matching
- Algorithms and Computation
- String distances and intrusion detection: Bridging the gap between formal languages and computer security
- How hard is to compute the edit distance
- Recognition of Noisy Subsequences Using Constrained Edit Distances
- Efficient algorithms for computing the inner edit distance of a regular language via transducers
- Computing the edit-distance between a regular language and a context-free language
- Prefix distance between regular languages
- Edit-distance between visibly pushdown languages
This page was built for publication: How hard is computing the edit distance?
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1854409)
