On the 𝑘-Hamming and 𝑘-Edit Distances
- Autori: Chiara Epifanio, Luca Forlizzi, Francesca Marzi, Filippo Mignosi, Giuseppe Placidi, Matteo Spezialetti
- Anno di pubblicazione: 2023
- Tipologia: Contributo in atti di convegno pubblicato in volume
- OA Link: http://hdl.handle.net/10447/619690
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.