La technique dite de complétion sur les automates d'arbre permet, à partir d'un automate d'arbre et d'un système de réécriture, de calculer une sur-approximation de l'ensemble des termes accessibles. Cette technique a été utilisée avec succès pour la vérification de protocoles de sécurité et, plus récemment, pour l'analyse des programmes Java. Comme dans toute approche de vérification par model-cheking, nous sommes confrontés à des problèmes d'explosion combinatoire lorsque les exemples deviennent plus conséquents. Dans cet article nous montrons comment faire face à cette situation en parallélisant et distribuant les calculs. Nous présentons aussi quelques résultats expérimentaux qui montrent que l'approche permet d'obtenir de meilleures performances en temps d'exécution.