Abstract FR:

Cette thèse constitue un point de départ pour une programmation parallèle des automates. Elle combine une approche séquentielle et une approche parallèle (sur le modèle PRAM) de l'analyse de ces algorithmes. On y trouve un nouvel algorithme séquentiel optimal de conversion d'une expression rationnelle en un automate ainsi que sa parallélisation (également optimale) un test d'appartenance d'un mot à un langage rationnel est développé, fournissant un algorithme parallèle efficace. Un algorithme séquentiel optimal, original de minimisation d'automate déterministe est décrit. De nouvelles techniques algorithmiques sont introduites tout au long de cette étude qui met en évidence l'apport réciproque des deux algorithmiques, séquentielle et parallèle.