Université Lille1 - Sciences et Technologies Automates comme outil de décision dans les arbres 005.131 Algorithmes Automates Langages formels Décidabilité (logique mathématique) Text Electronic Thesis or Dissertation fr 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. application/pdf 1 : 1 Mo https://pepite-depot.univ-lille.fr/RESTREINT/HDR/1990/50376-1990-198.pdf Tison Sophie 1900-01-01 080475205 1990-01-01 Mathématiques Université Lille1 - Sciences et Technologies 026404184 HDR non oui ddc:000 ASCII PDF 9999 restriction 2012-01-01 9999-01-01 restriction 2012-01-01 9999-01-01