From Cascade Decompositions to Bit-Vector Algorithms
© Elsevier



Anne Bergeron et Sylvie Hamel



Résumé :


     Un algorithme vectoriel est un algorithme qui applique à un vecteur d'entrée un nombre borné d'opérations vectorielles, indépendant de la longueur du vecteur d'entrée. Dans cet article, on décrit les liens entre l'existence d'algorithmes vectoriels et la décomposition en cascades d'automates "counter-free".

     On montre que tout calcul pouvant être exécuté par un automate "counter-free" peut être reformulé en terme d'un algorithme vectoriel. De plus, on montre que pour une classe d'automates liée à des algorithmes de bio-informatique, la complexité des algorithmes résultants est linéaire en le nombre de transitions de l'automate original.