Testing Distributional Properties of Context-Free Grammars

Alexander Clark
Proceedings of The 13th International Conference on Grammatical Inference, PMLR 57:42-53, 2017.

Abstract

Recent algorithms for distributional learning of context-free grammars can learn all languages defined by grammars that have certain distributional properties: the finite kernel property (FKP) and the finite context property (FCP). In this paper we present some algorithms for approximately determining whether a given grammar has one of these properties. We then present the results of some experiments that indicate that with randomly generated context-free grammars in Chomsky normal form, which generate infinite languages and are derivationally sparse, nearly all grammars have the finite kernel property, whereas the finite context property is much less common.

Cite this Paper

BibTeX
@InProceedings{pmlr-v57-clark16, title = {Testing Distributional Properties of Context-Free Grammars}, author = {Clark, Alexander}, booktitle = {Proceedings of The 13th International Conference on Grammatical Inference}, pages = {42--53}, year = {2017}, editor = {Verwer, Sicco and Zaanen, Menno van and Smetsers, Rick}, volume = {57}, series = {Proceedings of Machine Learning Research}, address = {Delft, The Netherlands}, month = {05--07 Oct}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v57/clark16.pdf}, url = {http://proceedings.mlr.press/v57/clark16.html}, abstract = {Recent algorithms for distributional learning of context-free grammars can learn all languages defined by grammars that have certain distributional properties: the finite kernel property (FKP) and the finite context property (FCP). In this paper we present some algorithms for approximately determining whether a given grammar has one of these properties. We then present the results of some experiments that indicate that with randomly generated context-free grammars in Chomsky normal form, which generate infinite languages and are derivationally sparse, nearly all grammars have the finite kernel property, whereas the finite context property is much less common.} }
Endnote
%0 Conference Paper %T Testing Distributional Properties of Context-Free Grammars %A Alexander Clark %B Proceedings of The 13th International Conference on Grammatical Inference %C Proceedings of Machine Learning Research %D 2017 %E Sicco Verwer %E Menno van Zaanen %E Rick Smetsers %F pmlr-v57-clark16 %I PMLR %P 42--53 %U http://proceedings.mlr.press/v57/clark16.html %V 57 %X Recent algorithms for distributional learning of context-free grammars can learn all languages defined by grammars that have certain distributional properties: the finite kernel property (FKP) and the finite context property (FCP). In this paper we present some algorithms for approximately determining whether a given grammar has one of these properties. We then present the results of some experiments that indicate that with randomly generated context-free grammars in Chomsky normal form, which generate infinite languages and are derivationally sparse, nearly all grammars have the finite kernel property, whereas the finite context property is much less common.
RIS
TY - CPAPER TI - Testing Distributional Properties of Context-Free Grammars AU - Alexander Clark BT - Proceedings of The 13th International Conference on Grammatical Inference DA - 2017/01/16 ED - Sicco Verwer ED - Menno van Zaanen ED - Rick Smetsers ID - pmlr-v57-clark16 PB - PMLR DP - Proceedings of Machine Learning Research VL - 57 SP - 42 EP - 53 L1 - http://proceedings.mlr.press/v57/clark16.pdf UR - http://proceedings.mlr.press/v57/clark16.html AB - Recent algorithms for distributional learning of context-free grammars can learn all languages defined by grammars that have certain distributional properties: the finite kernel property (FKP) and the finite context property (FCP). In this paper we present some algorithms for approximately determining whether a given grammar has one of these properties. We then present the results of some experiments that indicate that with randomly generated context-free grammars in Chomsky normal form, which generate infinite languages and are derivationally sparse, nearly all grammars have the finite kernel property, whereas the finite context property is much less common. ER -
APA
Clark, A.. (2017). Testing Distributional Properties of Context-Free Grammars. Proceedings of The 13th International Conference on Grammatical Inference, in Proceedings of Machine Learning Research 57:42-53 Available from http://proceedings.mlr.press/v57/clark16.html.

Related Material