Mircea Marin and Gabriel Istrate. Learning cover contextfree grammars from structural data. In Proceedings of the 11th International Colloquium on Theoretical Aspects of Computing, (ICTAC'14). Springer Verlag, Lecture Notes in Computer Science, 2014.
Abstract:
We consider the problem of learning an unknown contextfree grammar when the only knowledge available and of interest to the learner is about its structural descriptions with depth at most l. The goal is to learn a cover contextfree grammar (CCFG) with respect to l, that is, a CFG whose structural descriptions with depth at most l agree with those of the unknown CFG. We propose an algorithm, called
LA^l, that efficiently learns a CCFG using two types of queries: structural
equivalence and structural membership. We show that LA^l runs in time polynomial in the number of states of a minimal deterministic finite cover
tree automaton (DCTA) with respect to l.
This number is often much smaller than the number of states of a minimum deterministic finite tree automaton for the structural descriptions of the unknown grammar.
Keywords:
contextfree grammars, grammatical inference
URL:
http://link.springer.com/chapter/10.1007/9783319108827_15
Posted by
Gabriel Istrate
Back
