mlsanityData to 14 Oct 2026

On the k-Hamming and k-Edit Distances

arXiv 2306.09144 ↗First posted 15 Jun 2023cs.CC cs.CL cs.DScited by 0

Not on the map. Why?

Abstract (arXiv)

In this paper we consider the weighted k-Hamming and k-Edit distances, that are natural generalizations of the classical Hamming and Edit distances. As main results of this paper we prove that for any k≥ 2 the DECIS-k-Hamming problem is mathbbP-SPACE-complete and the DECIS-k-Edit problem is NEXPTIME-complete.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 3 of its 20 references that are in the map. First posted on arXiv 15 Jun 2023.

Builds on

3 of 20 references.

References · 3

  1. 2014Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)cited by 18
  2. 2015Adaptive Computation of the Swap-Insert Correction Distancecited by 1
  3. 2021Checking whether a word is Hamming-isometric in linear timecited by 1

Built on by

Not cited yet.