Learning efficiently (local) substitutable context-free languages from tex

3rd July 2015

Inria - Centre de Recherche Rennes, Bretagne Atlantique

2nd July, 2015 

Speaker: François Coste , researcher at ReGLiS team, INRIA Rennes-Bretagne, Rennes, France

Abstract: Using distributional learning approach in grammatical inference has been particularly fruitful in the recent years, especially to get nice theoretical learnability results for expressive context-free and mildly context-sensitive languages.

In this talk, we focus on turning this theory into practice. We introduce first the local substitutable languages, which were better suited for learning in our initial application of interest (characterizing protein sequences). We present then a generic efficient algorithm learning such languages from examples of sequences, allowing the inference from real sequences in reasonable time and producing more intelligible grammars than the classical approach. Back to theory, we finally show that this practical algorithm enables polynomial time and data identification in the limit from positive examples of this class of languages.