The intractability of computing the Hamming distance
From MaRDI portal
Publication:557834
DOI10.1016/j.tcs.2005.02.002zbMath1078.68044OpenAlexW2072141295MaRDI QIDQ557834
Bodo Manthey, K. Ruediger Reischuk
Publication date: 30 June 2005
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2005.02.002
Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
Information, possible worlds and the cooptation of scepticism ⋮ Consensus String Problem for Multiple Regular Languages ⋮ Closest substring problems for regular languages ⋮ Consensus string problem for multiple regular languages
Cites Work
- Fixed-parameter tractability and completeness II: On completeness for W[1]
- Approximating the minimum maximal independence number
- A faster algorithm computing string edit distances
- A survey of multiple sequence comparison methods
- The complexity of computing maximal word functions
- How hard is computing the edit distance?
- Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(\) and PSPACE analogues]
- Parity, circuits, and the polynomial-time hierarchy
- A sublinear algorithm for weakly approximating edit distance
- A linear space algorithm for computing maximal common subsequences
- On the Tape Complexity of Deterministic Context-Free Languages
- Algorithms on Strings, Trees and Sequences
- On the Amount of Nondeterminism and the Power of Verifying
- Error Detecting and Error Correcting Codes
- Syntax-directed least-errors analysis for context-free languages
- Fixed-Parameter Tractability and Completeness I: Basic Results
- The complexity of error-correcting codes
- Algorithms and Computation
- An error-correcting parse algorithm
- Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
- A Minimum Distance Error-Correcting Parser for Context-Free Languages
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
