Rémi Eyraud (EURISE, Univ. de St Etienne)

L’inférence grammaticale a pour but l’apprentissage automatique de langages formels. Jusqu’à la fin des années 90, l’attention des chercheurs de cette communauté s’est principalement focalisée sur les langages réguliers. Mais il est plus difficile de s’attaquer à l’inférence des langages hors-contextes, la classe de complexité suivante dans la hiérarchie de Chomsky. En effet, des barrières importantes ont été découvertes : plusieurs résultats théoriques montrent l’impossibilité d’apprendre l’intégralité de cette classe. Pourtant, dans de nombreux domaines, allant de la génétique au traitement des langues naturelles, en passant par la compression de texte et la recherche d'information, ce type de langages est nécessaire.

Lors de ce séminaire, les principaux résultats théoriques seront abordés. Un algorithme particulier sera ensuite détaillé ainsi qu'une application à la modélisation de l'acquisition de sa langue par l'enfant (grammaire anglaise).