Abstract FR:

En inférence grammaticale de langages réguliers, la notion de langages résiduels est au cœur des algorithmes existants, notamment par le biais du théorème de Myhill-Nerode. Nous menons ici une étude de cette notion qui nous conduit à définir une nouvelle classe d'automates non déterministes (AFN) : un Automate fini à États Résiduels (AFER) est un AFN dont tous les états définissent un langage résiduel du langage qu'il reconnaît. Nous présentons en détail cette classe d'automates ainsi que ses propriétés. En particulier, nous montrons que tout langage régulier est reconnu par un unique AFER canonique minimal en nombre d'états. Nous introduisons également deux opérateurs qui permettent conjointement de construire l'AFER canonique d'un langage à partir de n'importe quel AFER le reconnaissant : les opérateurs de réduction et de saturation. Nous complétons cette étude avec un ensemble d'expériences qui montrent que pour des langages générés aléatoirement selon certains protocoles, la représentation des langages par AFER est plus économique que par AFD. Une deuxième partie s'intéresse à l'utilisation de la notion d'AFER et des opérateurs de réduction et de saturation en inférence grammaticale de langages réguliers. Ceux-ci permettent alors d'introduire deux nouvelles approches algorithmiques : l'inférence par réduction, et l'inférence par saturation. Deux algorithmes illustrent ces méthodes : DeLeTe I et DeLeTe II. Nous montrons que ces algorithmes ont de bonnes propriétés à la fois sur le plan théorique et sur le plan expérimental. Le dernier chapitre de ce mémoire montre comment ces résultats pourraient être exploités dans d'autres domaines de l'inférence grammaticale et fait un tour d'horizon des recherches en cours qui prolongent les résultats de cette thèse.