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:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
