Learning local substitutable context-free languages from positive examples in polynomial time and data by reduction

François Coste, Jacques Nicolas
Proceedings of The 14th International Conference on Grammatical Inference 2018, PMLR 93:155-168, 2019.

Abstract

To study more formally the approach by reduction initiated by ReGLiS, we propose a formal characterization of the grammars in reduced normal form (RNF) which can be learned by this approach. A modification of the core of ReGLiS is then proposed to ensure returning RNF grammars in polynomial time. This enables us to show that local substitutable languages represented by RNF context-free grammars are identifiable in polynomial time and thick data (IPTtD) from positive examples.

Cite this Paper

BibTeX
@InProceedings{pmlr-v93-coste19a, title = {Learning local substitutable context-free languages from positive examples in polynomial time and data by reduction}, author = {Coste, Fran\c{c}ois and Nicolas, Jacques}, booktitle = {Proceedings of The 14th International Conference on Grammatical Inference 2018}, pages = {155--168}, year = {2019}, editor = {Unold, Olgierd and Dyrka, Witold and Wieczorek, Wojciech}, volume = {93}, series = {Proceedings of Machine Learning Research}, month = {feb}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v93/coste19a/coste19a.pdf}, url = {https://proceedings.mlr.press/v93/coste19a.html}, abstract = {To study more formally the approach by reduction initiated by ReGLiS, we propose a formal characterization of the grammars in reduced normal form (RNF) which can be learned by this approach. A modification of the core of ReGLiS is then proposed to ensure returning RNF grammars in polynomial time. This enables us to show that local substitutable languages represented by RNF context-free grammars are identifiable in polynomial time and thick data (IPTtD) from positive examples.} }
Endnote
%0 Conference Paper %T Learning local substitutable context-free languages from positive examples in polynomial time and data by reduction %A François Coste %A Jacques Nicolas %B Proceedings of The 14th International Conference on Grammatical Inference 2018 %C Proceedings of Machine Learning Research %D 2019 %E Olgierd Unold %E Witold Dyrka %E Wojciech Wieczorek %F pmlr-v93-coste19a %I PMLR %P 155--168 %U https://proceedings.mlr.press/v93/coste19a.html %V 93 %X To study more formally the approach by reduction initiated by ReGLiS, we propose a formal characterization of the grammars in reduced normal form (RNF) which can be learned by this approach. A modification of the core of ReGLiS is then proposed to ensure returning RNF grammars in polynomial time. This enables us to show that local substitutable languages represented by RNF context-free grammars are identifiable in polynomial time and thick data (IPTtD) from positive examples.
APA
Coste, F. & Nicolas, J.. (2019). Learning local substitutable context-free languages from positive examples in polynomial time and data by reduction. Proceedings of The 14th International Conference on Grammatical Inference 2018, in Proceedings of Machine Learning Research 93:155-168 Available from https://proceedings.mlr.press/v93/coste19a.html.

Related Material