A sharp criterion for criticality in probabilistic context-free grammars: which grammars produce power-law mutual-information decay?

Lin and Tegmark proved that the mutual information between two symbols in a sequence decays exponentially with separation for every probabilistic regular grammar, while there exist probabilistic context-free grammars (PCFGs) for which it decays as a power law $d^{-k}$ of the number $d$ of intervening symbols, with an explicit exponent for a specific subfamily. Since regular grammars are a strict subset of context-free grammars, not every context-free grammar is critical in this sense, and the authors left open the formulation of an even sharper criterion. The open problem is to characterize exactly which PCFGs exhibit such asymptotic power-law mutual-information decay — ideally through spectral and structural properties of the grammar's generation operator and the geometry of its derivation trees — separating them from grammars whose mutual information decays exponentially or tends to a nonzero constant.

Background

A context-free grammar (CFG) generates strings by repeatedly rewriting nonterminal symbols via production rules, producing a derivation tree whose leaves form the terminal string; a probabilistic context-free grammar (PCFG) attaches probabilities to the rules, making the derivation a random process. The mutual information $I(d)$ between two symbols separated by $d$ intervening symbols measures how much knowing one symbol reveals about the other; if $I(d)$ decays as a power law $d^{-k}$ rather than exponentially, the generated language is called critical, by analogy with critical points in statistical mechanics where correlations become long-ranged. Lin and Tegmark introduced a tractable surrogate, the rational mutual information $I_R$, computed from rational functions of the symbol-transition operator $G$ (the matrix of conditional probabilities relating a parent nonterminal to its child), and proved two endpoints. First, for any Markov chain or hidden Markov model (a Markov chain whose internal states are observed only through stochastic output symbols) with irreducible and aperiodic transition matrix, $I(d)$ decays exponentially at a rate set by the second-largest eigenvalue $\lambda_2$ of the transition matrix; since probabilistic regular grammars are equivalent to hidden Markov models, no probabilistic regular grammar is critical. Second (their Theorem 3, proved in their Appendix C for a subfamily with $G$ irreducible, aperiodic, and non-degenerate), there exist PCFGs whose terminal-symbol mutual information decays exactly like $d^{-k}$ with an explicit exponent $k$. Their argument combines exponential decay of correlations with structural distance in the derivation tree, $\sim e^{-\gamma \Delta}$, with the geometric relation between structural distance $\Delta$ and sequential distance $d$ in balanced trees, $d \sim e^{\mu \Delta}$, so that $e^{-\gamma \Delta} \sim d^{-\gamma/\mu}$. The general claim that context-free grammars can produce power-law correlations is argued semi-heuristically via Chomsky normal form (the restricted grammar form in which every production is either $A \to BC$ or $A \to a$). Because regular grammars are a strict subset of context-free grammars, the class of PCFGs splits into critical and non-critical members, but the two theorems only pin down the extremes: no criterion is known that, given an arbitrary consistent PCFG, decides on which side it falls.

Problem Statement

Given a consistent probabilistic context-free grammar $\mathcal{G}$ (one whose derivations terminate with probability 1), consider the mutual information $I(d)$ between two terminal symbols in the generated string as a function of the number $d$ of symbols between them. Lin and Tegmark proved that no probabilistic regular grammar has $I(d)$ decaying as a power law, and that a specific subfamily of PCFGs has $I(d) \sim d^{-k}$ with explicitly computable $k$. Formulate and prove a sharp criterion that, for an arbitrary PCFG, decides whether it is critical — i.e., whether $I(d)$ decays asymptotically as a power law $d^{-k}$ with $k > 0$ — as opposed to decaying exponentially or tending to a nonzero constant. The criterion should be expressed in terms of properties of the grammar, such as the spectral properties of its generation operator (including degenerate, reducible, or periodic cases), the branching structure of its rules, and the geometry of its derivation trees (e.g., how sequential distance grows with structural distance), and it must reproduce the two known endpoints: probabilistic regular grammars are never critical, and the subfamily of Theorem 3 of Lin and Tegmark is critical with the computed exponent.

References

1. Henry W. Lin and Max Tegmark, "Critical Behavior in Physics and Probabilistic Formal Languages", Entropy 19(7):299 (2017). DOI: 10.3390/e19070299, https://doi.org/10.3390/e19070299 (preprint: arXiv:1606.06737, "Criticality in Formal Languages and Statistical Physics", https://arxiv.org/abs/1606.06737)
2. Kai Nakaishi and Koji Hukushima, "Absence of Phase Transition in Random Language Model", Physical Review Research 4, 023156 (2022). DOI: 10.1103/PhysRevResearch.4.023156, https://doi.org/10.1103/PhysRevResearch.4.023156 (preprint: arXiv:2105.00832, https://arxiv.org/abs/2105.00832)
3. Kai Nakaishi and Koji Hukushima, "Statistical properties of probabilistic context-sensitive grammars", Physical Review Research 6, 033216 (2024). DOI: 10.1103/PhysRevResearch.6.033216, https://doi.org/10.1103/PhysRevResearch.6.033216 (preprint: arXiv:2402.07113, https://arxiv.org/abs/2402.07113)
4. Kai Nakaishi, Ryo Yoshida, Kohei Kajikawa, Koji Hukushima, and Yohei Oseki, "Rethinking the Relationship between the Power Law and Hierarchical Structures", arXiv:2505.04984 (2025), https://arxiv.org/abs/2505.04984
5. Huitao Shen, "Mutual Information Scaling and Expressive Power of Sequence Models", arXiv:1905.04271 (2019), https://arxiv.org/abs/1905.04271
6. Francesca Fernandes and Matilde Marcolli, "Formal languages, spin systems, and quasicrystals", Journal of Geometry and Physics 216, 105568 (2025). DOI: 10.1016/j.geomphys.2025.105568, https://doi.org/10.1016/j.geomphys.2025.105568
7. Eric De Giuli, "Emergence of order in random languages", Journal of Physics A: Mathematical and Theoretical 52, 504001 (2019). DOI: 10.1088/1751-8121/ab293c, https://doi.org/10.1088/1751-8121/ab293c