Inscriere cercetatori

Perioada scursă de la depunerea aplicațiilor

Proiecte de cercetare postdoctorala (PD)

Proiecte complexe de cercetare de frontiera (PCCF)

Site nou !

Daca nu va puteti recupera parola (sau aveti alte probleme), scrieti-ne la pagina de contact. Situl vechi se gaseste la adresa


Learning cover context-free grammars from structural data

Domenii publicaţii > Ştiinţe informatice + Tipuri publicaţii > Articol în volumul unei conferinţe

Autori: Mircea Marin and Gabriel Istrate

Editorial: Springer Verlag, Lecture Notes in Computer Science, Proceedings of the 11th International Colloquium on Theoretical Aspects of Computing (ICTAC'14), Lecture Notes in Computer Science, Springer Verlag, 2014.


We consider the problem of learning an unknown context-free 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 context-free 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.

Cuvinte cheie: context-free grammars, grammatical inference