Statistical properties of probabilistic context-sensitive grammars
Open Access
- 26 August 2024
- journal article
- research article
- Published by American Physical Society (APS) in Physical Review Research
- Vol. 6 (3) , 033216
Abstract
Probabilistic context-free grammars (PCFGs), which are commonly used to generate trees randomly, have been well analyzed theoretically, leading to applications in various domains. Despite their utility, the distributions that the grammar can express are limited to those in which the distribution of a subtree depends only on its root and not on its context. This limitation presents a challenge for modeling various real-world phenomena, such as natural languages. To overcome this limitation, a probabilistic context-sensitive grammar (PCSG) is introduced, where the distribution of a subtree depends on its context. Numerical analysis of a PCSG reveals that the distribution of a symbol does not constitute a qualitative difference from that in the context-free case, but mutual information does. Furthermore, a novel metric introduced to directly quantify the breaking of this limitation detects a distinct difference between PCFGs and PCSGs. This metric, applicable to an arbitrary distribution of a tree, allows for further investigation and characterization of various tree structures that PCFGs cannot express. Published by the American Physical Society 2024Keywords
All Related Versions
Funding Information
- Japan Society for the Promotion of Science (23KJ0622, 23H01095)
- Japan Science and Technology Corporation (JPMJPF2221)
- University of Tokyo
This publication has 30 references indexed in Scilit:
- Statistical Universals of Language2021
- A strongly polynomial algorithm for criticality of branching processes and consistency of stochastic context-free grammarsInformation Processing Letters, 2013
- An Introduction to the Bootstrap1993
- Mutual information functions versus correlation functionsJournal of Statistical Physics, 1990
- Combinatory grammars and parasitic gapsNatural Language & Linguistic Theory, 1987
- The complexity of the vocabulary of BambaraLinguistics and Philosophy, 1985
- Evidence against the context-freeness of natural languageLinguistics and Philosophy, 1985
- Finite size scaling analysis of ising model block distribution functionsZeitschrift für Physik B Condensed Matter, 1981
- Mathematical models for cellular interactions in development II. Simple and branching filaments with two-sided inputsJournal of Theoretical Biology, 1968
- Mathematical models for cellular interactions in development I. Filaments with one-sided inputsJournal of Theoretical Biology, 1968