Voulez-vous effacer les recherches récentes ?

Toutes les recherches récentes seront supprimées

Regarder en plein écran

Seminaire CSI LRDE - Antoine Pietri

EPITA
il y a 5 ans|45 vues
Recherche de mots synchronisants dans un DFA

Le problème de recherche de mots synchronisants les plus courts possibles est un problème important qui a beaucoup d’applications (orienteurs mécaniques, problème de coloration de route, vérification de modèles, bioinformatique, 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 possibles en temps polynomial. Dans cet exposé, nous comparerons les différentes approches utilisées par les algorithmes principaux les plus connus (Glouton et Cycle, SynchroP et SynchroPL), en termes de complexité spatiale et temporelle, et les résultats effectifs (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.

https://www.lrde.epita.fr/wiki/CSI_Seminar_2014-07-10

Vidéos à découvrir