Titre :

On Distances between Words with Parameters

Auteur(s) :

Bourhis, Pierre [Auteur]
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Self-adaptation for distributed services and large software systems [SPIRALS]
Boussidan, Aaron [Auteur]
Laboratoire d'Informatique Gaspard-Monge [LIGM]
Gambette, Philippe [Auteur]
Laboratoire d'Informatique Gaspard-Monge [LIGM]

Éditeur(s) ou directeur(s) scientifique(s) :

Laurent Bulteau
Zsuzsanna Lipták

Titre de la manifestation scientifique :

CPM 2023

Ville :

Champs-sur-Marne, Marne-la-Vallée

Pays :

France

Date de début de la manifestation scientifique :

2023-06-26

Titre de l’ouvrage :

LIPIcs

Titre de la revue :

Proceedings of the 34th Annual Symposium on Combinatorial Pattern Matching

Éditeur :

Schloss Dagstuhl

Date de publication :

2023

Mot(s)-clé(s) en anglais :

String matching
edit distance
Levenshtein
parameterized matching
parameterized words
parameter words
instantiable words
NP-completeness
MAX-SAT

Discipline(s) HAL :

Informatique [cs]/Algorithme et structure de données [cs.DS]

Résumé en anglais : [en]

The edit distance between parameterized words is a generalization of the classical edit distance where it is allowed to map particular letters of the first word, called parameters, to parameters of the second word before ...
Lire la suite >The edit distance between parameterized words is a generalization of the classical edit distance where it is allowed to map particular letters of the first word, called parameters, to parameters of the second word before computing the distance. This problem has been introduced in particular for detection of code duplication, and the notion of words with parameters has also been used with different semantics in other fields. The complexity of several variants of edit distances between parameterized words has been studied, however, the complexity of the most natural one, the Levenshtein distance, remained open. In this paper, we solve this open question and close the exhaustive analysis of all cases of parameterized word matching and function matching, showing that these problems are np-complete. To this aim, we also provide a comparison of the different problems, exhibiting several equivalences between them. We also provide and implement a MaxSAT encoding of the problem, as well as a simple FPT algorithm in the alphabet size, and study their efficiency on real data in the context of theater play structure comparison.Lire moins >

Langue :

Anglais

Comité de lecture :

Oui

Audience :

Internationale

Vulgarisation :

Non

Projet ANR :

Requêtes Ontologiques Complexes sur des Fédérations de Données Hétérogènese

Collections :

• Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189

Source :

Harvested from HAL