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 P-SPACE-complete and the DECIS-k-Edit problem is NEXPTIMEcomplete. In our formulation, weights are included in the instance description and the cost is not uniform.
On the k-Hamming and k-Edit Distances
Luca Forlizzi;Francesca Marzi;Filippo Mignosi;Giuseppe Placidi;Matteo Spezialetti
2023-01-01
Abstract
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 P-SPACE-complete and the DECIS-k-Edit problem is NEXPTIMEcomplete. In our formulation, weights are included in the instance description and the cost is not uniform.File in questo prodotto:
| File | Dimensione | Formato | |
|---|---|---|---|
|
8136.pdf
accesso aperto
Tipologia:
Documento in Versione Editoriale
Licenza:
Creative commons
Dimensione
1.05 MB
Formato
Adobe PDF
|
1.05 MB | Adobe PDF | Visualizza/Apri |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
