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 = {Alexander Clark}, booktitle = {Proceedings of The 13th International Conference on Grammatical Inference}, pages = {42--53}, year = {2017}, editor = {Sicco Verwer and Menno van Zaanen and Rick Smetsers}, 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 %J Proceedings of Machine Learning Research %P 42--53 %U http://proceedings.mlr.press %V 57 %W PMLR %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 PY - 2017/01/16 DA - 2017/01/16 ED - Sicco Verwer ED - Menno van Zaanen ED - Rick Smetsers ID - pmlr-v57-clark16 PB - PMLR SP - 42 DP - PMLR 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 PMLR 57:42-53

Related Material