Emergence of order in random languages

Abstract

We consider languages generated by weighted context-free grammars. It is shown that the behaviour of large texts is controlled by saddle-point equations for an appropriate generating function. We then consider ensembles of grammars, in particular the Random Language Model of E. DeGiuli, Phys. Rev. Lett., 122, 128301, 2019. This model is solved in the replica-symmetric ansatz, which is valid in the high-temperature, disordered phase. It is shown that in the phase in which languages carry information, the replica symmetry must be broken.

16 pages + 2 appendices; v2: references added and some explanations expanded. v3: Corrigendum added as Appendix B

References in corpus (1)

• Random Language Model

Cited by in corpus (7)

• Dynamical mean-field theory: from ecosystems to reaction networks
• Breakdown of random matrix universality in Markov models
• Boosting Vector Calculus with the Graphical Notation
• Absence of Phase Transition in Random Language Model
• Statistical properties of probabilistic context-sensitive grammars
• Robustness of the Random Language Model
• Entangled criticality and irreversibility in random Markov dynamics