Overview of Context Free Grammatical Inference

Over the last few years, with a number of collaborators I have published several results on grammatical inference of non-regular languages; typically subclasses of context free grammars. This is just a brief road-map to some of the papers; I will write a proper overview at some point. For some ideological background, read my invited paper at LATA 2010.

My basic view is that the key problem is the complexity theoretic one of constructing the representation, rather than the information theoretic problems.

Congruence based results

First we have some results using the same representational idea: constructing a context free grammar, where the non-terminals correspond to congruence classes.
  1. The most basic result is the learnability of context free substitutable languages. This is a positive data only result, where the data is adversarially chosen; the most difficult learning environment possible. We get a polynomial result for a limited class of context free languages, that does not include all finite languages. This appeared in ALT 2005, and a journal version in JMLR. This was work with Remi Eyraud, while he was visiting here at RHUL.
  2. Yoshinaka extended this result to k-l-substitutable languages.
  3. The next result, not chronologically but conceptually, is the query learning result for congruential context free grammars at ICGI 2010. This is strictly polynomial result for exact learning from membership queries and equivalence queries -- this is the Minimally Adequate Teacher model of Angluin. This result gives us a class of context free languages that properly includes the class of regular languages.
  4. We also have a PAC result for a smaller class of languages, the unambiguous NTS languages. This is from positive data alone; and appeared at ICGI, 2006.
These papers together give a fairly complete theory analogous to the now classical theory of regular grammatical inference by Angluin; however the class does not include all context free languages. Still in the class of context free languages, we have a dual result, where we base the representation on contexts rather than subclasses. This is in ICGI 2010 as well. The class we get includes all regular languages and also has some non-deterministic and inherently ambiguous languages.

A transitional result

We now have a transitional result which uses a context-sensitive formalism to get a context-free result. This used Binary Feature Grammars; it uses as a representation slightly larger sets: the class of all strings whose distributions contain the distribution of a given string. This is the first paper that starts to exploit the lattice structure of the congruence classes. This appeared at ICGI 2008, and was joint work with Remi and Amaury Habrard.

Slightly Context sensitive results

Distributional lattice grammars complete the direction that Binary feature grammars started: the first paper is in FG 2009, and another in CoNLL 2010.

Multiple context free grammars

Finally we have a switch to truly context-sensitive representations; Yoshinaka showed how this could be done in a paper at ALT 2009, with a polynomial positive data result; extending the substitutability method. This gives a nice result but for an even more limited class of languages.


Alexander Clark alexc@cs.rhul.ac.uk