A Hierarchy of Context-Free Languages Learnable from Positive Data and Membership Queries

Makoto Kanazawa, Ryo Yoshinaka
Proceedings of the Fifteenth International Conference on Grammatical Inference, PMLR 153:18-31, 2021.

Abstract

We consider a generalization of the “dual” approach to distributional learning of context-free grammars, where each nonterminal A is associated with a string set XA characterized by a finite set C of contexts. Rather than letting XA be the set of all strings accepted by all contexts in C as in previous works, we allow more flexible uses of the contexts in C, using some of them positively (contexts that accept the strings in XA) and others negatively (contexts that do not accept any strings in XA). The resulting more general algorithm works in essentially the same way as before, but on a larger class of context-free languages.

Cite this Paper

BibTeX
@InProceedings{pmlr-v153-kanazawa21a, title = {A Hierarchy of Context-Free Languages Learnable from Positive Data and Membership Queries}, author = {Kanazawa, Makoto and Yoshinaka, Ryo}, booktitle = {Proceedings of the Fifteenth International Conference on Grammatical Inference}, pages = {18--31}, year = {2021}, editor = {Chandlee, Jane and Eyraud, Rémi and Heinz, Jeff and Jardine, Adam and van Zaanen, Menno}, volume = {153}, series = {Proceedings of Machine Learning Research}, month = {23--27 Aug}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v153/kanazawa21a/kanazawa21a.pdf}, url = {https://proceedings.mlr.press/v153/kanazawa21a.html}, abstract = {We consider a generalization of the “dual” approach to distributional learning of context-free grammars, where each nonterminal $A$ is associated with a string set $X_A$ characterized by a finite set $C$ of contexts. Rather than letting $X_A$ be the set of all strings accepted by all contexts in $C$ as in previous works, we allow more flexible uses of the contexts in $C$, using some of them positively (contexts that accept the strings in $X_A$) and others negatively (contexts that do not accept any strings in $X_A$). The resulting more general algorithm works in essentially the same way as before, but on a larger class of context-free languages. } }
Endnote
%0 Conference Paper %T A Hierarchy of Context-Free Languages Learnable from Positive Data and Membership Queries %A Makoto Kanazawa %A Ryo Yoshinaka %B Proceedings of the Fifteenth International Conference on Grammatical Inference %C Proceedings of Machine Learning Research %D 2021 %E Jane Chandlee %E Rémi Eyraud %E Jeff Heinz %E Adam Jardine %E Menno van Zaanen %F pmlr-v153-kanazawa21a %I PMLR %P 18--31 %U https://proceedings.mlr.press/v153/kanazawa21a.html %V 153 %X We consider a generalization of the “dual” approach to distributional learning of context-free grammars, where each nonterminal $A$ is associated with a string set $X_A$ characterized by a finite set $C$ of contexts. Rather than letting $X_A$ be the set of all strings accepted by all contexts in $C$ as in previous works, we allow more flexible uses of the contexts in $C$, using some of them positively (contexts that accept the strings in $X_A$) and others negatively (contexts that do not accept any strings in $X_A$). The resulting more general algorithm works in essentially the same way as before, but on a larger class of context-free languages.
APA
Kanazawa, M. & Yoshinaka, R.. (2021). A Hierarchy of Context-Free Languages Learnable from Positive Data and Membership Queries. Proceedings of the Fifteenth International Conference on Grammatical Inference, in Proceedings of Machine Learning Research 153:18-31 Available from https://proceedings.mlr.press/v153/kanazawa21a.html.

Related Material