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 $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.

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