Paper Info
Title
Learning Cover Context-Free Grammars from Structural Data.
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 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.
Year
DOI
Venue
2014
10.1007/978-3-319-10882-7_15
Lecture Notes in Computer Science
Keywords
DocType
Volume
automata theory and formal languages,structural descriptions,grammatical inference
Journal
8687
Issue
ISSN
Citations 
2
0302-9743
0
PageRank 
References 
Authors
0.34
10
2
Name
Order
Citations
PageRank
Mircea Marin18117.67
Gabriel Istrate29924.96