In this paper we consider the weighted 𝑘-Hamming and 𝑘-Edit distances, that are natural generalizations of the classical Hamming and Edit distances. As main results of this paper we prove that for any 𝑘 ≥ 2 the DECIS-𝑘-Hamming problem is P-SPACE-complete and the DECIS-𝑘-Edit problem is NEXPTIMEcomplete. In our formulation, weights are included in the instance description and the cost is not uniform.
Chiara Epifanio, L.F. (2023). On the 𝑘-Hamming and 𝑘-Edit Distances. In G. Castiglione, M. Sciortino (a cura di), ICTCS 2023-Italian Conference on Theoretical Computer Science 2023 Proceedings of the 24th Italian Conference on Theoretical Computer Science Palermo, Italy, September 13-15, 2023 (pp. 143-156).
On the 𝑘-Hamming and 𝑘-Edit Distances
Chiara Epifanio;Filippo Mignosi;
2023-12-13
Abstract
In this paper we consider the weighted 𝑘-Hamming and 𝑘-Edit distances, that are natural generalizations of the classical Hamming and Edit distances. As main results of this paper we prove that for any 𝑘 ≥ 2 the DECIS-𝑘-Hamming problem is P-SPACE-complete and the DECIS-𝑘-Edit problem is NEXPTIMEcomplete. In our formulation, weights are included in the instance description and the cost is not uniform.
| File | Dimensione | Formato | |
|---|---|---|---|
|
8136.pdf
accesso aperto
Descrizione: On the 𝑘-Hamming and 𝑘-Edit Distances
Tipologia:
Versione Editoriale
Dimensione
1.05 MB
Formato
Adobe PDF
|
1.05 MB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
