Recherche de petits mots synchronisants

Auteurs

Antoine Pietri

Type

techreport

Année

2014

Numéro

1402

Résumé

Le probléme de recherche de mots synchronisants les plus courts possible est un probléme important qui a beaucoup d'applications (orienteurs mécaniques, probléme de coloration de route, vérification de modélesbioinformatique, protocoles réseaux, etc.) Un mot synchronisant (ou une séquence de réinitialisation) pour un automate fini déterministe est une séquence d'étiquettes qui envoie n'importe quel état de l'automate d'entrée à un seul et même état. Trouver le plus court mot synchronisant dans un automate général est NP-complet, c'est pourquoi la plupart des algorithmes sont des heuristiques qui cherchent à trouver des mots les plus courts possible en temps polynomial. Dans ce rapport, nous comparerons les différentes approches utilisées par les algorithmes principaux les plus connus (Glouton, Cycle, SynchroP, SynchroPL et FastSynchro), en terme de complexité spatiale et temporelle, et les résultats empiriques (longueur moyenne des mots trouvés, temps utilisé par l'algorithme en moyenne). Nous discuterons aussi des différentes représentations intermédiaires utilisées par ces algorithmes, et comment utiliser les informations qu'elles contiennent.