Université Lille1 - Sciences et Technologies Automates d'arbres avec tests d'égalites Tree automata with equality tests 005.131 Automates Text Electronic Thesis or Dissertation fr 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. application/pdf 1 : 1 Mo https://pepite-depot.univ-lille.fr/LIBRE/Th_Num/1990/50376-1990-301.pdf Bogaert Bruno 1900-01-01 13904387X 1990-01-01 Informatique Université Lille1 - Sciences et Technologies 026404184 Doctorat non oui Tison Sophie 080475205 ddc:000 ASCII PDF 9999