Massively parallel computing model in MapReduce for some problems in automata theory

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.In this thesis, we tackle some known problems in automata theory using parallel approaches in large scale context, namely the composition of weighted finite state machines and the derivation of distinguishing sequences for nondeterministic finite state machines. We adopt in our study a theoretical model of parallel processing called the massive parallel computing model in MapReduce (MPC-MR) where the only cost is given by the amount of communication between the nodes of a cluster and the number of iterations of the algorithm. We have proposed efficient large-scale parallel MapReduce algorithms based on MPC-MR model for each of the addressed problems. The obtained results show clearly that the MPC-MR model offers a guaranteed theoretical framework for the development of new efficient parallel algorithms in automata theory