Learning local substitutable context-free languages from positive examples in polynomial time and data by reduction


François Coste, Jacques Nicolas ;
Proceedings of The 14th International Conference on Grammatical Inference 2018, PMLR 93:155-168, 2019.


To study more formally the approach by reduction initiated by ReGLiS, we propose a formal characterization of the grammars in reduced normal form (RNF) which can be learned by this approach. A modification of the core of ReGLiS is then proposed to ensure returning RNF grammars in polynomial time. This enables us to show that local substitutable languages represented by RNF context-free grammars are identifiable in polynomial time and thick data (IPTtD) from positive examples.

Related Material