Recherche de petits mots synchronisants

From LRDE

Revision as of 17:06, 9 January 2018 by Bot (talk | contribs) (Created page with "{{CSIReportFR | authors = Antoine Pietri | titre = Recherche de petits mots synchronisants | year = 2014 | number = 1402 | resume = Le probléme de recherche de mots synchroni...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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.