Abstract FR:

Cette thèse examine les possibilités et les performances de la recherche sur les mots et les arbres en parallèle. La première partie traite de la recherche de mots dans un texte, sur les modèles Pram et hyper cube. Nous présentons un nouvel algorithme qui réalise cette recherche en temps o(log n) sur un hyper cube Simd, montrant qu'il est possible d'atteindre le minima temporel pour ce problème. La seconde partie examine la recherche parallèle de motifs dans les arbres. Nous généralisons des techniques sur les automates d'arbres. Finalement, la dernière partie expose les principes d'un langage fonctionnel parallèle base sur la recherche d'arbres, et elle décrit l'implémentation de ce langage sur la connection machine cm-2