Abstract FR:

L'inference grammaticale peut etre vue comme le probleme de l'identification d'un langage a partir d'exemples et de contre-exemples de mots de ce langage. Ce probleme a surtout ete etudie pour les langages reguliers, qui ne peuvent rendre compte que de structures syntaxiques simples. Parmi les methodes d'inference de grammaires regulieres, les methodes par enumeration procedent en explorant un ensemble de grammaires a la recherche d'une solution. L'enumeration s'effectue selon une relation d'ordre definie sur cet ensemble, ce qui permet l'elagage de larges regions de l'espace de recherche. Nous montrons dans cette these que ce principe peut s'appliquer a l'inference de grammaires algebriques. Les possibilites offertes par deux relations d'ordre classiques, la couverture de reynolds et l'inclusion structurelle, sont examinees. Pour chacune de ces relations, des operateurs permettant de parcourir l'espace sont definis. Nous definissons dans un premier temps l'operateur correspondant a la couverture de reynolds: la fission de non terminaux. Un algorithme d'inference par enumeration utilisant cette relation est ensuite mise en uvre. L'inclusion structurelle est une relation plus complexe, pour laquelle la specification d'operateurs est difficile. Le choix de la forme normale inversible pour les grammaires de l'espace de recherche nous permet de decider de leur inclusion en temps polynomial, et de definir deux operateurs pouvant servir de base a un algorithme d'inference par enumeration: substitution sur la partie gauche d'une regle, et suppression d'une regle. Ces operateurs ne permettent pas de parcourir tout l'espace, aussi toutes les solutions ne sont pas toujours atteintes. Les mecanismes proposes pour l'inclusion structurelle constituent un compromis entre rapidite et exhaustivite de l'enumeration, et visent plus a la discrimination des exemples et contre-exemples de l'echantillon qu'a l'obtention de toutes les solutions au probleme d'inference