• Langue : Français
• Discipline : Mathématiques
• Identifiant : Inconnu
• Type de mémoire : Habilitation à diriger des recherches
• Date de soutenance : 01/01/1990

Résumé en langue originale

Le cadre de cette étude est la reconnaissabilité et les automates d'arbres. On peut résumer l'essentiel de notre démarche en quelques mots : étudier les ensembles d'arbres d'un point de vue algébrique et utiliser les résultats de cette approche à des fins algorithmiques. (Mieux on connaît la structure des choses mieux on les manipule!). Les automates d'arbres peuvent être considérés comme un puissant outil de décision, le théorème de Rabin étant sans doute le résultat qui illustre le mieux cette démarche : la preuve est basée sur les automates d'arbres mais le résultat permet de prouver la décidabilité d'un grand nombre d'autres théories. D'unepart, nous utilisons ici ces méthodes à la fois classiques et méconnues pour prouver que la théorie de la réécriture close est décidable. D'autre part, nous définissons une nouvelle classe de reconnaisseurs, les automates avec tests d'égalité ; la famille correspondante de langages d'arbres est une extension réélle de la famille des reconnaissables, tout en conservant la plupart de ses bonnes propriétés : elle est close pour les opérations booléennes, et le problème du vide y est décidable. Nous obtenons d'autres résultats (décidabilité de l'arrêt équitable d'un système de réécriture clos, liens entre reconnaissabilité et non linéarité) qui à la fois illustrent le succès de ces techniques et soulignent quelques points encore obscurs dans la structure des arbres.