Fast Implementations of
Automata Computations © Springer-Verlag



Anne Bergeron et Sylvie Hamel



Résumé :


     G.Myers a récemment décrit un algorithme basé sur les vecteurs de bits pour le calcul de la distance d'édition entre deux chaînes de caractères. Cet algorithme convertir une chaîne d'entrée de taille n en une chaîne de sortie de taille n d'une façon parallèle, en utilisant des opérations standards sur les vecteurs de bits.

     Dans cet article, nous généralisons cette technique et nous donnons une caractérisation d'une classe d'automates pour lesquels il existe un algorithme parallèle équivalent. En guise d'application, nous donnons une extension du résultat de Myers au calcul de distances valuées entre deux chaînes de caractères. Ce type de distance est couramment employé pour l'exploration des immenses banques de données générées par les projets de séquençage génétique.