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.
Epifanio, C., Forlizzi, L., Marzi, F., Mignosi, F., Placidi, G., Spezialetti, M. (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;
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.
