Identification of Substitutable Context-Free Languages over Infinite Alphabets from Positive Data

Yutaro Numaya, Diptarama Hendrian, Ryo Yoshinaka, Ayumi Shinohara
Proceedings of 16th edition of the International Conference on Grammatical Inference, PMLR 217:23-34, 2023.

Abstract

This paper is concerned with the identification in the limit from positive data of substitutable context-free languages \textsc{cfl}s) over infinite alphabets. citet{ClarkE07} showed that substitutable \textsc{cfl}s over finite alphabets are learnable in this learning paradigm. We show that substitutable \textsc{cfl}s generated by grammars whose production rules may have \emph{predicates} that represent sets of potentially infinitely many terminal symbols in a compact manner are learnable if the terminal symbol sets represented by those predicates are learnable, under a certain condition. This can be seen as a result parallel to citeauthor{ArgyrosDA2018}’s work (2018) that amplifies the query learnability of predicate classes to that of symbolic automata classes. Our result is the first that shows such amplification is possible for identifying some \textsc{cfl}s in the limit from positive data.

Cite this Paper

BibTeX
@InProceedings{pmlr-v217-numaya23a, title = {Identification of Substitutable Context-Free Languages over Infinite Alphabets from Positive Data}, author = {Numaya, Yutaro and Hendrian, Diptarama and Yoshinaka, Ryo and Shinohara, Ayumi}, booktitle = {Proceedings of 16th edition of the International Conference on Grammatical Inference}, pages = {23--34}, year = {2023}, editor = {Coste, François and Ouardi, Faissal and Rabusseau, Guillaume}, volume = {217}, series = {Proceedings of Machine Learning Research}, month = {10--13 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v217/numaya23a/numaya23a.pdf}, url = {https://proceedings.mlr.press/v217/numaya23a.html}, abstract = {This paper is concerned with the identification in the limit from positive data of substitutable context-free languages \textsc{cfl}s) over infinite alphabets. citet{ClarkE07} showed that substitutable \textsc{cfl}s over finite alphabets are learnable in this learning paradigm. We show that substitutable \textsc{cfl}s generated by grammars whose production rules may have \emph{predicates} that represent sets of potentially infinitely many terminal symbols in a compact manner are learnable if the terminal symbol sets represented by those predicates are learnable, under a certain condition. This can be seen as a result parallel to citeauthor{ArgyrosDA2018}’s work (2018) that amplifies the query learnability of predicate classes to that of symbolic automata classes. Our result is the first that shows such amplification is possible for identifying some \textsc{cfl}s in the limit from positive data.} }
Endnote
%0 Conference Paper %T Identification of Substitutable Context-Free Languages over Infinite Alphabets from Positive Data %A Yutaro Numaya %A Diptarama Hendrian %A Ryo Yoshinaka %A Ayumi Shinohara %B Proceedings of 16th edition of the International Conference on Grammatical Inference %C Proceedings of Machine Learning Research %D 2023 %E François Coste %E Faissal Ouardi %E Guillaume Rabusseau %F pmlr-v217-numaya23a %I PMLR %P 23--34 %U https://proceedings.mlr.press/v217/numaya23a.html %V 217 %X This paper is concerned with the identification in the limit from positive data of substitutable context-free languages \textsc{cfl}s) over infinite alphabets. citet{ClarkE07} showed that substitutable \textsc{cfl}s over finite alphabets are learnable in this learning paradigm. We show that substitutable \textsc{cfl}s generated by grammars whose production rules may have \emph{predicates} that represent sets of potentially infinitely many terminal symbols in a compact manner are learnable if the terminal symbol sets represented by those predicates are learnable, under a certain condition. This can be seen as a result parallel to citeauthor{ArgyrosDA2018}’s work (2018) that amplifies the query learnability of predicate classes to that of symbolic automata classes. Our result is the first that shows such amplification is possible for identifying some \textsc{cfl}s in the limit from positive data.
APA
Numaya, Y., Hendrian, D., Yoshinaka, R. & Shinohara, A.. (2023). Identification of Substitutable Context-Free Languages over Infinite Alphabets from Positive Data. Proceedings of 16th edition of the International Conference on Grammatical Inference, in Proceedings of Machine Learning Research 217:23-34 Available from https://proceedings.mlr.press/v217/numaya23a.html.

Related Material