Titre original :

Automates d'arbres avec tests d'égalites

  • Langue : Français
  • Discipline : Informatique
  • Identifiant : Inconnu
  • Type de thèse : Doctorat
  • Date de soutenance : 01/01/1990

Résumé en langue originale

Dans la classe des ensembles rationnels d'arbres, les automates permettent de décider de l'appartenance d'un terme. Ils sont assimilables àa une signature dans les algèbres sortées initiales. Nous proposons une extension des automates d'arbres, en ajoutant à chaque règle une condition portant sur les égalités entre termes frères. Nous définissons deux classes d'automates. Dans la première, les règles ne peuvent imposer que des égalités, pas de différences. La classe des forêts reconnues coïncide alors avec celle des algèbres à signature non-linéaire. Une deuxième classe, strictement plus large, est obtenue en permettant d'imposer des différences. Il s'agit alors d'une algèbre de Boole, close par morphismes alphabétiques d'arbres. Nous prouvons que chaque forêt peut être reconnue par un automate à tests déterministe, et que l'on peut décider si la forêt reconnue par un automate à tests est vide. La propriété du vide est NP-dure dans le cas général. Nous donnons un algorithme de complexité polynomiale dans le cas où les automates sont déterministes.

  • Directeur(s) de thèse : Tison, Sophie

AUTEUR

  • Bogaert, Bruno
Droits d'auteur : Ce document est protégé en vertu du Code de la Propriété Intellectuelle.
Accès libre