TY - GEN
T1 - Learning conjunctive grammars and contextual binary feature grammars
AU - Yoshinaka, Ryo
N1 - Publisher Copyright:
© Springer International Publishing Switzerland 2015.
PY - 2015
Y1 - 2015
N2 - Approaches based on the idea generically called distributional learning have been making great success in the algorithmic learning of context-free languages and their extensions. We in this paper show that conjunctive grammars are also learnable by a distributional learning technique. Conjunctive grammars are context-free grammars enhanced with conjunctive rules to extract the intersection of two languages. We also compare our result with the closely related work by Clark et al. (JMLR 2010) on contextual binary feature grammars (CBFGs). Our learner is stronger than theirs. In particular our learner learns every exact CBFG, while theirs does not. Clark et al. emphasized the importance of exact CBFGs but they only conjectured there should be a learning algorithm for exact CBFGs. This paper shows that their conjecture is true.
AB - Approaches based on the idea generically called distributional learning have been making great success in the algorithmic learning of context-free languages and their extensions. We in this paper show that conjunctive grammars are also learnable by a distributional learning technique. Conjunctive grammars are context-free grammars enhanced with conjunctive rules to extract the intersection of two languages. We also compare our result with the closely related work by Clark et al. (JMLR 2010) on contextual binary feature grammars (CBFGs). Our learner is stronger than theirs. In particular our learner learns every exact CBFG, while theirs does not. Clark et al. emphasized the importance of exact CBFGs but they only conjectured there should be a learning algorithm for exact CBFGs. This paper shows that their conjecture is true.
KW - Algorithmic learning
KW - Distributional Learning
KW - Grammatical inference
UR - http://www.scopus.com/inward/record.url?scp=84928777982&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84928777982&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-15579-1_49
DO - 10.1007/978-3-319-15579-1_49
M3 - Conference contribution
AN - SCOPUS:84928777982
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 623
EP - 635
BT - Language and Automata Theory and Applications - 9th International Conference, LATA 2015, Proceedings
A2 - Dediu, Adrian-Horia
A2 - Martín-Vide, Carlos
A2 - Formenti, Enrico
A2 - Truthe, Bianca
PB - Springer Verlag
T2 - 9th International Conference on Language and Automata Theory and Applications, LATA 2015
Y2 - 2 March 2015 through 6 March 2015
ER -