We show that the mutual information between two symbols, as a function of the
number of symbols between the two, decays exponentially in any probabilistic
regular grammar, but can decay like a power law for a context-free grammar.
This result about formal languages is closely related to a well-known result in
classical statistical mechanics that there are no phase transitions in
dimensions fewer than two. It is also related to the emergence of power-law
correlations in turbulence and cosmological inflation through recursive
generative processes. We elucidate these physics connections and comment on
potential applications of our results to machine learning tasks like training
artificial recurrent neural networks. Along the way, we introduce a useful
quantity which we dub the rational mutual information and discuss
generalizations of our claims involving more complicated Bayesian networks.

该研究论文阐述了对于正则文法的符号间互信息随符号间距离指数衰减的特性，然而对于上下文无关文法则符合幂律分布；并且将该现象与统计力学、湍流以及宇宙膨胀等领域的幂律相关性做了联系，以及阐述了这种现象在机器学习中的潜在应用。除此之外，该研究论文还提出了一种合理的互信息量的量化方式，并探讨了该现象在更复杂的贝叶斯网络中的推广。

形式语言和统计物理学中的临界性

Criticality in Formal Languages and Statistical Physics

Motivated by a concrete problem and with the goal of understanding the sense
in which the complexity of streaming algorithms is related to the complexity of
formal languages, we investigate the problem Dyck(s) of checking matching
parentheses, with $s$ different types of parenthesis.
We present a one-pass randomized streaming algorithm for Dyck(2) with space
$\Order(\sqrt{n}\log n)$, time per letter $\polylog (n)$, and one-sided error.
We prove that this one-pass algorithm is optimal, up to a $\polylog n$ factor,
even when two-sided error is allowed. For the lower bound, we prove a direct
sum result on hard instances by following the "information cost" approach, but
with a few twists. Indeed, we play a subtle game between public and private
coins. This mixture between public and private coins results from a balancing
act between the direct sum result and a combinatorial lower bound for the base
case.
Surprisingly, the space requirement shrinks drastically if we have access to
the input stream in reverse. We present a two-pass randomized streaming
algorithm for Dyck(2) with space $\Order((\log n)^2)$, time $\polylog (n)$ and
one-sided error, where the second pass is in the reverse direction. Both
algorithms can be extended to Dyck(s) since this problem is reducible to
Dyck(2) for a suitable notion of reduction in the streaming model.

研究了检查匹配括号问题 Dyck (s) ，提出了一个时间复杂度为 $\polylog (n)$、空间复杂度为 $\Order (\sqrt {n}\log n)$ 的单项式随机流算法，证明当允许双边误差时，此算法是最优的，甚至可以通过一些扭曲来证明一些困难实例的直和结果和基本情况下的组合下界之间的平衡。而当可以倒序访问输入流时，空间需求会显著缩小。