Ad Astra Awards
Ad Astra Journal
Science library
White book
University rankings
Who's who
Publications
Theses and dissertations
Ad Astra association
 
Press releases
News
Events
Funding opportunities
 
Login
Registration
 
>> Românã
 
   
 

Mircea Marin and Gabriel Istrate. Learning cover context-free 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 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.

Keywords: context-free grammars, grammatical inference

URL: http://link.springer.com/chapter/10.1007/978-3-319-10882-7_15

Posted by Gabriel Istrate

Back

   
© Ad Astra 2001-2013