Abstract FR:

Nous considérons un problème d'inférence grammaticale. Celui-ci peut être formulé comme la tâche de découvrir un concept caractérisant un ensemble de séquences, appelé aussi langage, à partir de séquences exemple. Afin de caractériser un langage, nous considérons une représentation sous forme d'automates finis non déterministes (NFA). Ceux-ci, bien que plus difficilement manipulables que les automates déterministes (DFA) habituellement utilisés, possèdent pour avantage d'être compactes et explicites (i. E. Interprétables par un expert du domaine d'application). Nous décrivons l'espace de recherche pour les NFAs, ainsi que pour différentes sous-classes des NFAs. On propose un algorithme pour l'inférence d'automates non ambigus (UFA) qui nécessite moins de données que les algorithmes usuels d'inférence de DFA pour converger. Nous proposons aussi des méthodes permettant d'introduire, dans l'inférence, des connaissances provenant de l'application (pour nous la bioinformatique).