Massively parallel computing model in MapReduce for some problems in automata theory
Bilal El Ghadyry · theses.fr (ABES) · 2022
Dans cette thèse, nous étudions l’algorithmique parallèle à grande échelle de quelques problèmes en théorie des automates, à savoir la composition des machines à états finis pondérées, ainsi que la dérivation des séquences séparantes à partir des machines à états finis non déterministes. Nous adoptons dans notre étude, un modèle théorique de traitement parallèle récemment introduit appelé modèle de calcul massivement parallèle en MapReduce (CMP-MR) où le seul coût est donné par la quantité de communication entre les nœuds et le nombre d’itérations de l’algorithme. Nous avons proposé des algorithmes parallèles efficaces à grande échelle en MapReduce basés sur le modèle CMP-MR pour chacun des problèmes traités. Les résultats obtenus montrent clairement que le modèle CMP-MR offre un cadre théorique garanti pour le développement denouveaux algorithmes parallèles efficaces à grande échelle en théorie des automates.