Régnier
Le Jeudi 3 Février 2000 à 14h30
au LRI, Salle 101
(INRIA)
Complexité du comptage des mots exceptionnels
Résumé/Abstract :
L'évaluation de la fréquence des occurrences d'un ensemble
donné de mots a de nombreuses applications et a été
très largement étudié récemment, notamment
dans le contexte de l'analyse de l'ADN. Les formules explicites
proposées par divers auteurs posent un problème de
calculabilité effective. Nous définissons un automate,
l'automate de corrélation, qui minimise la complexité de calcul.
Ceci est crucial pour les applications pratiques, notamment l'extraction de
motifs. Cette approche permet de traiter le modèle markovien.
Nous étudions en particulier les expressions régulières
et les motifs approchés.