Inscriere cercetatori

Daca aveti cont Ad Astra si de Facebook, intrati pe pagina de profil pentru a da dreptul sa va logati pe site doar cu acest buton.

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.


Want create site? Find Free WordPress Themes and plugins.

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.

Did you find apk for android? You can find new Free Android Games and apps.

Cuvinte cheie: context-free grammars, grammatical inference