Université Lille1 - Sciences et Technologies De l'apport des langages résiduels en inférence grammaticale de langages réguliers On the contribution of residual languages in grammatical inference of regular languages 005.131 Langages de programmation Linguistique Informatique Apprentissage automatique Text Electronic Thesis or Dissertation 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. application/pdf 1 : 1 Mo https://pepite-depot.univ-lille.fr/RESTREINT/Th_Num/2002/50376-2002-203.pdf Lemay Aurélien 1900-01-01 069891281 2002LIL10082 2002-01-01 Informatique Université Lille1 - Sciences et Technologies 026404184 Doctorat non oui Terlutte Alain 034197281 Denis François 103914803 ddc:000 ASCII PDF 9999 restriction 2012-01-01 9999-01-01 restriction 2012-01-01 9999-01-01