mlsanityData to 14 Oct 2026

Criticality in Formal Languages and Statistical Physics

arXiv 1606.06737 ↗First posted 21 Jun 2016cond-mat.dis-nn cs.CLcited by 35

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 35 papers in the map (data through 14 Oct 2026). First posted on arXiv 21 Jun 2016.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 6; 2022: 1; 2023: 3; 2024: 6; 2025: 10; 2026: 9.

35 papers.

Sort:

By area:

  1. 2021Hyperbolic Deep Neural Networks: A Surveycited by 139
  2. 2024Towards a theory of how the structure of language is acquired by deep neural networkscited by 39
  3. 2026Deriving Neural Scaling Laws from the statistics of natural languagecited by 23
  4. 2021Tensor networks and efficient descriptions of classical datacited by 13
  5. 2023Humans and language models diverge when predicting repeating textcited by 13
  6. 2024Phase transition in large language models and the criticality of natural languagescited by 13
  7. 2025L2M: Mutual Information Scaling Law for Long-Context Language Modelingcited by 9
  8. 2021Slower is Better: Revisiting the Forgetting Mechanism in LSTM for Slower Information Decaycited by 7
  9. 2021Explainable Natural Language Processing with Matrix Product Statescited by 7
  10. 2025Scaling Laws and Representation Learning in Simple Hierarchical Languages: Transformers vs. Convolutional Architecturescited by 5
  11. 2025Next-token pretraining implies in-context learningcited by 5
  12. 2024Tree-Planted Transformers: Unidirectional Transformer Language Models with Implicit Syntactic Supervisioncited by 4
23 more
  1. 2021Do Data-based Curricula Work?cited by 3
  2. 2024Quantum Algorithms for Compositional Text Processingcited by 3
  3. 2025States of LLM-generated Texts and Phase Transitions between themcited by 3
  4. 2025Human-like fleeting memory improves language learning but impairs reading time prediction in transformer language modelscited by 3
  5. 2026Causal Autoregressive Diffusion Language Modelcited by 3
  6. 2021Actionable Entities Recognition Benchmark for Interactive Fictioncited by 2
  7. 2025Correlation Dimension of Auto-Regressive Large Language Modelscited by 2
  8. 2024Vygotsky Distance: Measure for Benchmark Task Similaritycited by 1
  9. 2025Rethinking the Relationship between the Power Law and Hierarchical Structurescited by 1
  10. 2025Gradual Forgetting: Logarithmic Compression for Extending Transformer Context Windowscited by 1
  11. 2026Probing How Scalable Table Data Enhances General Long-Context Reasoningcited by 1
  12. 2026Generative Criticality in Large Language Model Temperature Scalingcited by 1
  13. 2022On Unsupervised Training of Link Grammar Based Language Modelscited by 0
  14. 2023Long Text Generation Challengecited by 0
  15. 2023Strahler Number of Natural Language Sentences in Comparison with Random Treescited by 0
  16. 2024Entangling Machine Learning with Quantum Tensor Networkscited by 0
  17. 2025Overfitting has a limitation: a model-independent generalization gap bound based on R'enyi entropycited by 0
  18. 2025SymSeqBench: a unified framework for the generation and analysis of rule-based symbolic sequences and datasetscited by 0
  19. 2026Turbulence-like 5/3 spectral scaling in contextual representations of language as a complex systemcited by 0
  20. 2026A scaling law of contextual persistence in human languagecited by 0
  21. 2026Do Quantum Models Scale Like LLMs?cited by 0
  22. 2026Writing as a Self-Organized Critical Processcited by 0
  23. 2026Learning to Learn a Languagecited by 0