Elamur Research⌕
☰
home / papers / 2025 / Between Circuits and Chomsky: Pre-pretraining on Formal Languages Imparts Linguistic Biases

Between Circuits and Chomsky: Pre-pretraining on Formal Languages Imparts Linguistic Biases

Paper · 2025 · Michael Y. Hu, Jackson Petty, Chuan Shi et al.

Summary

Transformer language models need far more data than humans. This paper asks which properties of a formal language make it a useful warm-up before natural-language training, a setup the authors call pre-pretraining. They propose two criteria, drawing on the Chomsky hierarchy and on circuit complexity. First, the language should encode hierarchical dependencies like those in syntax. Second, it should be definable in C-RASP, a logic tied to what transformers can learn and length-generalize.

They pre-pretrain transformers on several formal languages, including 1-Dyck, 𝑘-Dyck, 𝑘-Shuffle Dyck and the copy language 𝑤𝑤. These are compared against three baselines: no pre-pretraining, random binary strings, and an equal amount of natural language. Most runs use 160M-parameter models, with a scale-up to 1B.

Languages with hierarchical structure gave lower natural-language loss and better linguistic generalization than the alternatives. Support for the C-RASP criterion was weaker. Attention heads learned during pre-pretraining stayed important for syntactic performance afterward. The approach offers a cheap, reusable initialization that improves data efficiency.

Key points

  • With a 1B-parameter model trained on about 1.6B natural-language tokens, pre-pretraining on 𝑘-Shuffle Dyck reached the baseline's final loss using 33% fewer tokens. It also generalized better linguistically.
  • 𝑘-Shuffle Dyck is context-sensitive and C-RASP-definable. It beat 𝑘-Dyck, which is not C-RASP-definable, clearly on only one evaluation, but it needed fewer pre-pretraining steps. 𝑘-Dyck came out nearly as strong overall.
  • The copy language 𝑤𝑤 hurt performance, even though it is context-sensitive. It has cross-serial dependencies but no hierarchy and is not definable in C-RASP.
  • One formal-language token replaced more than one natural-language token, so the marginal rate of substitution exceeded 1. This means formal data outperformed extra in-distribution text.
  • Code is available at github.com/michahu/pre-pretraining. Stated limitations:
    • Training was blocked (formal language first, then natural language) rather than mixed.
    • Only English was tested, a data-rich language.
    • Only transformers were studied.
    • Effects beyond 1B parameters are untested.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🎓New York UniversityNew York · United States219 works · 103,487 citations

 Fields, topics and concepts

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 18,614 worksArtificial Intelligence · 17,965 worksArts and Humanities · 17,450 worksLanguage and Linguistics · 17,296 works

🧭 Topics 1Research subjects and languages the work is about.Language models & pretraining · 3,894 works

Cite

Cite as Michael Y. Hu, Jackson Petty, Chuan Shi, William Merrill and Tal Linzen. 2025. Between Circuits and Chomsky: Pre-pretraining on Formal Languages Imparts Linguistic Biases. Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers).

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.18653/v1/2025.acl-long.478

@inproceedings{hu2025between,
  title = {{Between Circuits and Chomsky: Pre-pretraining on Formal Languages Imparts Linguistic Biases}},
  author = {Michael Y. Hu, Jackson Petty, Chuan Shi, William Merrill and Tal Linzen},
  booktitle = {Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)},
  year = {2025},
  doi = {10.18653/v1/2025.acl-long.478},
  url = {https://doi.org/10.18653/v1/2025.acl-long.478}
}

References

79 references, 16 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Yoshua Bengio, Jérôme Louradour, Ronan Collobert, and Jason Weston. 2009. Curriculum learning. In Proceedings of the 26th Annual International Conference on Machine Learning, ICML ’09, page 41–48, New York, NY, USA. Association for Computing Machinery.
  2. Adithya Bhaskar, Dan Friedman, and Danqi Chen. 2024. The heuristic core: Understanding subnetwork generalization in pretrained language models. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 14351–14368, Bangkok, Thailand. As… find
  3. Stella Biderman, Hailey Schoelkopf, Quentin Anthony, Herbie Bradley, Kyle O’Brien, Eric Hallahan, Mohammad Aflah Khan, Shivanshu Purohit, USVSN Sai Prashanth, Edward Raff, Aviya Skowron, Lintang Sutawika, and Oskar Van Der Wal. 2023. Pythia: a suite for analyzing large language models across trainin… find
  4. Loubna Ben Allal, Anton Lozhkov, Elie Bakouch, Gabriel Martín Blázquez, Guilherme Penedo, Lewis Tunstall, Andrés Marafioti, Hynek Kydlíček, Agustín Piqueres Lajarín, Vaibhav Srivastav, Joshua Lochner, Caleb Fahlgren, Xuan-Son Nguyen, Clémentine Fourrier, Ben Burtenshaw, Hugo Larcher, Haojun Zhao, C… — SmolLM2: When Smol Goes Big — Data-Centric Training of a Small Language Model
  5. Alexandra Butoi, Ghazal Khalighinejad, Anej Svete, Josef Valvoda, Ryan Cotterell, and Brian DuSell. 2025. Training Neural Networks as Recognizers of Formal Languages. In The Thirteenth International Conference on Learning Representations. find
  6. Kristijan Armeni, Christopher Honey, and Tal Linzen. 2022. Characterizing verbatim short-term memory in neural language models. In Proceedings of the 26th Conference on Computational Natural Language Learning (CoNLL), pages 405–424, Abu Dhabi, United Arab Emirates (Hybrid). Association for Computati… find
  7. Cheng-Han Chiang and Hungyi Lee. 2022. On the Transferability of Pre-trained Language Models: A Study from Artificial Datasets. In The Thirty-Sixth AAAI Conference on Artificial Intelligence (AAAI-22). find
  8. Kristijan Armeni, Marko Pranjić, and Senja Pollak. 2024. Transformer verbatim in-context retrieval across time and scale. In Proceedings of the 28th Conference on Computational Natural Language Learning, pages 56–68, Miami, FL, USA. Association for Computational Linguistics. find
  9. Noam Chomsky. 1959. On Certain Formal Properties of Grammars. Information and Control, 2(2):137–167. find
  10. Viraat Aryabumi, Yixuan Su, Raymond Ma, Adrien Morisot, Ivan Zhang, Acyr Locatelli, Marzieh Fadaee, Ahmet Üstün, and Sara Hooker. 2025. To Code or Not To Code? Exploring Impact of Code in Pre-training. In The Thirteenth International Conference on Learning Representations. find
  11. Y Bar-Hillel, M Perles, and E Shamir. 1961. On formal properties of simple phrase structure grammars. Language Typology and Universals, 14:143–172. find
  12. Nora Belrose, Quintin Pope, Lucia Quirke, Alex Troy Mallen, and Xiaoli Fern. 2024. Neural Networks Learn Statistics of Increasing Complexity. In Forty-first International Conference on Machine Learning. find
  13. Mayee F Chen, Michael Y. Hu, Nicholas Lourie, Kyunghyun Cho, and Christopher Re. 2025. Aioli: A Unified Optimization Framework for Language Model Data Mixing. In The Thirteenth International Conference on Learning Representations. find
  14. Noam Chomsky. 1956. Three models for the description of language. IRE Transactions on Information Theory, 2(3):113–124. find
  15. Noam Chomsky and M.P. Schützenberger. 1959. The Algebraic Theory of Context-Free Languages. In P. Braffort and D. Hirschberg, editors, Computer Programming and Formal Systems, volume 26 of Studies in Logic and the Foundations of Mathematics, pages 118–161. Elsevier. find
  16. Ameet Deshpande, Partha Talukdar, and Karthik Narasimhan. 2022. When is BERT multilingual? isolating crucial ingredients for cross-lingual transfer. In Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, page… find
  17. Chelsea Finn, Pieter Abbeel, and Sergey Levine. 2017. Model-agnostic meta-learning for fast adaptation of deep networks. In Proceedings of the 34th International Conference on Machine Learning - Volume 70, ICML’17, page 1126–1135. JMLR.org.
  18. Yiding Hao, Dana Angluin, and Robert Frank. 2022. Formal Language Recognition by Hard Attention Transformers: Perspectives from Circuit Complexity. Transactions of the Association for Computational Linguistics, 10:800–810.
  19. Hansi Hettiarachchi, Tharindu Ranasinghe, Paul Rayson, Ruslan Mitkov, Mohamed Gaber, Damith Premasiri, Fiona Anting Tan, and Lasitha Randunu Chandrakantha Uyangodage. 2025. Overview of the First Workshop on Language Models for Low-Resource Languages (LoResLM 2025). In Proceedings of the First Worksh… find
  20. John E Hopcroft, Rajeev Motwani, and Jeffrey D Ullman. 2006. Introduction to automata theory, languages, and computation, 3 edition. Pearson. find
  21. Michael Y. Hu, Aaron Mueller, Candace Ross, Adina Williams, Tal Linzen, Chengxu Zhuang, Ryan Cotterell, Leshem Choshen, Alex Warstadt, and Ethan Gotlieb Wilcox. 2024. Findings of the Second BabyLM Challenge: Sample-Efficient Pretraining on Developmentally Plausible Corpora. In The 2nd BabyLM Challen… find
  22. Xinting Huang, Andy Yang, Satwik Bhattamishra, Yash Sarrof, Andreas Krebs, Hattie Zhou, Preetum Nakkiran, and Michael Hahn. 2025. A Formal Framework for Understanding Length Generalization in Transformers. In The Thirteenth International Conference on Learning Representations. find
  23. Yiding Jiang, Allan Zhou, Zhili Feng, Sadhika Malladi, and J Zico Kolter. 2025. Adaptive Data Optimization: Dynamic Sample Selection with Scaling Laws. In The Thirteenth International Conference on Learning Representations. find
  24. Najoung Kim and Tal Linzen. 2020. COGS: A compositional generalization challenge based on semantic interpretation. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 9087–9105, Online. Association for Computational Linguistics. find
  25. Najoung Kim, Sebastian Schuster, and Shubham Toshniwal. 2024. Code Pretraining Improves Entity Tracking Abilities of Language Models. Preprint, arXiv:2405.21068. — [arXiv:2405.21068](https://arxiv.org/abs/2405.21068) find
  26. Tomasz Korbak, Kejian Shi, Angelica Chen, Rasika Bhalerao, Christopher L. Buckley, Jason Phang, Samuel R. Bowman, and Ethan Perez. 2023. Pre-training language models with human preferences. In Proceedings of the 40th International Conference on Machine Learning, ICML’23. JMLR.org. find
  27. Sreejan Kumar, Ishita Dasgupta, Raja Marjieh, Nathaniel D. Daw, Jonathan D. Cohen, and Thomas L. Griffiths. 2022. Disentangling Abstraction from Statistical Pattern Matching in Human and Machine Learning. PLOS Computational Biology, 19. find
  28. S.-Y. Kuroda. 1964. Classes of languages and Linear-Bounded Automata. Information and Control, 7(2):207–223. find
  29. Yann LeCun, Ido Kanter, and Sara A. Solla. 1991. Eigenvalues of covariance matrices: Application to neural-network learning. Physical Review Letters, 66:2396–2399. find
  30. Bingzhi Li, Lucia Donatelli, Alexander Koller, Tal Linzen, Yuekun Yao, and Najoung Kim. 2023. SLOG: A structural generalization benchmark for semantic parsing. In Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, pages 3213–3232, Singapore. Association for Compu… find
  31. Lisha Li, Kevin Jamieson, Giulia DeSalvo, Afshin Rostamizadeh, and Ameet Talwalkar. 2017. Hyperband: a novel bandit-based approach to hyperparameter optimization. Journal of Machine Learning Research, 18(1):6765–6816. find
  32. David Lindner, Janos Kramar, Sebastian Farquhar, Matthew Rahtz, Thomas McGrath, and Vladimir Mikulik. 2023. Tracr: Compiled Transformers as a Laboratory for Interpretability. In Thirty-seventh Conference on Neural Information Processing Systems. find
  33. Qin Liu, Fei Wang, Chaowei Xiao, and Muhao Chen. 2024. From shortcuts to triggers: Backdoor defense with denoised PoE. In Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers), pages 483–… find
  34. Rebecca Marvin and Tal Linzen. 2018. Targeted syntactic evaluation of language models. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pages 1192–1202, Brussels, Belgium. Association for Computational Linguistics. find
  35. R Thomas McCoy, Erin Grant, Paul Smolensky, Thomas L Griffiths, and Tal Linzen. 2020a. Universal linguistic inductive biases via meta-learning. In Proceedings of the 42nd Annual Conference of the Cognitive Science Society, pages 737–743. find
  36. R. Thomas McCoy and Thomas L. Griffiths. 2025. Modeling rapid language learning by distilling Bayesian priors into artificial neural networks. Nature Communications. find
  37. R. Thomas McCoy, Junghyun Min, and Tal Linzen. 2020b. BERTs of a feather do not generalize together: Large variability in generalization across models with similar test set performance. In Proceedings of the Third BlackboxNLP Workshop on Analyzing and Interpreting Neural Networks for NLP, pages 217–… find
  38. Tom McCoy, Ellie Pavlick, and Tal Linzen. 2019. Right for the wrong reasons: Diagnosing syntactic heuristics in natural language inference. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 3428–3448, Florence, Italy. Association for Computational Ling…
  39. William Merrill, Jackson Petty, and Ashish Sabharwal. 2024. The Illusion of State in State-Space Models. In Forty-first International Conference on Machine Learning. find
  40. William Merrill and Ashish Sabharwal. 2023. A Logic for Expressing Log-Precision Transformers. In Thirty-seventh Conference on Neural Information Processing Systems. find
  41. William Merrill, Nikolaos Tsilivis, and Aman Shukla. 2023. A Tale of Two Circuits: Grokking as Competition of Sparse and Dense Subnetworks. Preprint, arXiv:2303.11873. — [arXiv:2303.11873](https://arxiv.org/abs/2303.11873) find
  42. William Merrill, Gail Weiss, Yoav Goldberg, Roy Schwartz, Noah A. Smith, and Eran Yahav. 2020. A formal hierarchy of RNN architectures. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 443–459, Online. Association for Computational Linguistics. find
  43. David A. Mix Barrington, Neil Immerman, and Howard Straubing. 1990. On uniformity within NC1. Journal of Computer and System Sciences, 41(3):274–306. find
  44. Aaron Mueller and Tal Linzen. 2023. How to plant trees in language models: Data and architectural effects on the emergence of syntactic inductive biases. In Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 11237–11252, Toronto, Ca… find
  45. Niklas Muennighoff, Alexander M. Rush, Boaz Barak, Teven Le Scao, Aleksandra Piktus, Nouamane Tazi, Sampo Pyysalo, Thomas Wolf, and Colin Raffel. 2023. Scaling Data-Constrained Language Models. In Proceedings of the 37th International Conference on Neural Information Processing Systems, NeurIPS ’23,… find
  46. Ryo Nakamura, Ryu Tadokoro, Ryosuke Yamada, Yuki M. Asano, Iro Laina, Christian Rupprecht, Nakamasa Inoue, Rio Yokota, and Hirokatsu Kataoka. 2024. Scaling Backwards: Minimal Synthetic Pre-Training? In Computer Vision – ECCV 2024: 18th European Conference, Milan, Italy, September 29–October 4, 2024,… find
  47. Alex Nichol, Joshua Achiam, and John Schulman. 2018. On First-Order Meta-Learning Algorithms. ArXiv, abs/1803.02999. find
  48. Team OLMo, Pete Walsh, Luca Soldaini, Dirk Groeneveld, Kyle Lo, Shane Arora, Akshita Bhagia, Yuling Gu, Shengyi Huang, Matt Jordan, Nathan Lambert, Dustin Schwenk, Oyvind Tafjord, Taira Anderson, David Atkinson, Faeze Brahman, Christopher Clark, Pradeep Dasigi, Nouha Dziri, Michal Guerquin, Hamish I… find
  49. Long Ouyang, Jeff Wu, Xu Jiang, Diogo Almeida, Carroll L. Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, John Schulman, Jacob Hilton, Fraser Kelton, Luke Miller, Maddie Simens, Amanda Askell, Peter Welinder, Paul Christiano, Jan Leike, and Ryan Lowe. 2022. Train…
  50. Isabel Papadimitriou and Dan Jurafsky. 2020. Learning Music Helps You Read: Using transfer to study linguistic structure in language models. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 6829–6839, Online. Association for Computational Lingu… find
  51. Isabel Papadimitriou and Dan Jurafsky. 2023. Injecting structural hints: Using language models to study inductive biases in language learning. In Findings of the Association for Computational Linguistics: EMNLP 2023, pages 8402–8413, Singapore. Association for Computational Linguistics. find
  52. Jill Gilkersonand Jeffrey A. Richardsand Steven F. Warrenand Judith K. Montgomeryand Charles R. Greenwoodand D. Kimbrough Ollerand John H. L. Hansenand Terrance D. Paul. 2017. Mapping the Early Language Environment Using All-Day Recordings and Automated Analysis. American Journal of Speech-Language… find
  53. Jackson Petty, Sjoerd van Steenkiste, and Tal Linzen. 2025. How Does Code Pretraining Affect Language Model Task Performance? Transactions on Machine Learning Research. find
  54. Yada Pruksachatkun, Jason Phang, Haokun Liu, Phu Mon Htut, Xiaoyi Zhang, Richard Yuanzhe Pang, Clara Vania, Katharina Kann, and Samuel R. Bowman. 2020. Intermediate-task transfer learning with pretrained language models: When and why does it work? In Proceedings of the 58th Annual Meeting of the Ass…
  55. Colin Raffel, Noam M. Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu. 2019. Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer. Journal of Machine Learning Research, 21:140:1–140:67.
  56. Sebastian Ruder, Matthew E. Peters, Swabha Swayamdipta, and Thomas Wolf. 2019. Transfer learning in natural language processing. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Tutorials, pages 15–18, Minneapolis, Minnesota. Assoc…
  57. Andrew M. Saxe, James L. McClelland, and Surya Ganguli. 2014. Exact solutions to the nonlinear dynamics of learning in deep linear neural networks. In International Conference on Learning Representations.
  58. Gail Weiss, Yoav Goldberg, and Eran Yahav. 2021. Thinking Like Transformers. In Proceedings of the 38th International Conference on Machine Learning, volume 139, pages 11080–11090. find
  59. Thibault Sellam, Steve Yadlowsky, Ian Tenney, Jason Wei, Naomi Saphra, Alexander D’Amour, Tal Linzen, Jasmijn Bastings, Iulia Raluca Turc, Jacob Eisenstein, Dipanjan Das, and Ellie Pavlick. 2022. The MultiBERTs: BERT Reproductions for Robustness Analysis. In International Conference on Learning Repr… find
  60. Ethan Gotlieb Wilcox, Michael Hu, Aaron Mueller, Alex Warstadt, Leshem Choshen, Chengxu Zhuang, Adina Williams, Ryan Cotterell, and Tal Linzen. 2025. Bigger is not always better: The importance of human-scale language modeling for psycholinguistics. Journal of Memory and Language. find
  61. Stuart M. Shieber. 1985. Evidence against the context-freeness of natural language. Linguistics and Philosophy, 8:333–343. find
  62. Mengzhou Xia, Zexuan Zhong, and Danqi Chen. 2022. Structured pruning learns compact and accurate models. In Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 1513–1528, Dublin, Ireland. Association for Computational Linguistics.
  63. Lena Strobl, William Merrill, Gail Weiss, David Chiang, and Dana Angluin. 2024. What formal languages can transformers express? a survey. Transactions of the Association for Computational Linguistics, 12:543–561. find
  64. Mirac Suzgun, Yonatan Belinkov, Stuart Shieber, and Sebastian Gehrmann. 2019. LSTM networks can perform dynamic counting. In Proceedings of the Workshop on Deep Learning and Formal Languages: Building Bridges, pages 44–54, Florence. Association for Computational Linguistics.
  65. Kevin Swersky, Jasper Snoek, and Ryan P. Adams. 2013. Multi-task Bayesian Optimization. In Neural Information Processing Systems. find
  66. Vladimir Naumovich Vapnik. 2000. The Nature of Statistical Learning Theory. In Statistics for Engineering and Information Science. find
  67. Pablo Villalobos, Anson Ho, Jaime Sevilla, Tamay Besiroglu, Lennart Heim, and Marius Hobbhahn. 2024. Will we run out of data? Limits of LLM scaling based on human-generated data. Preprint, arXiv:2211.04325.
  68. Alex Warstadt, Aaron Mueller, Leshem Choshen, Ethan Wilcox, Chengxu Zhuang, Juan Ciro, Rafael Mosquera, Bhargavi Paranjabe, Adina Williams, Tal Linzen, and Ryan Cotterell. 2023. Findings of the BabyLM challenge: Sample-efficient pretraining on developmentally plausible corpora. In Proceedings of the… find
  69. Alex Warstadt, Alicia Parrish, Haokun Liu, Anhad Mohananey, Wei Peng, Sheng-Fu Wang, and Samuel R. Bowman. 2020a. BLiMP: The benchmark of linguistic minimal pairs for English. Transactions of the Association for Computational Linguistics, 8:377–392.
  70. Andy Yang and David Chiang. 2024. Counting Like Transformers: Compiling Temporal Counting Logic Into Softmax Transformers. In First Conference on Language Modeling. find
  71. Andy Yang, David Chiang, and Dana Angluin. 2024. Masked Hard-Attention Transformers Recognize Exactly the Star-Free Languages. In The Thirty-eighth Annual Conference on Neural Information Processing Systems. find
  72. Greg Yang, J. Edward Hu, Igor Babuschkin, Szymon Sidor, Xiaodong Liu, David Farhi, Nick Ryder, Jakub W. Pachocki, Weizhu Chen, and Jianfeng Gao. 2022. Tensor Programs V: Tuning Large Neural Networks via Zero-Shot Hyperparameter Transfer. ArXiv, abs/2203.03466. find
  73. Fred Zhang and Neel Nanda. 2024. Towards Best Practices of Activation Patching in Language Models: Metrics and Methods. In The Twelfth International Conference on Learning Representations.
  74. Tianyang Zhong, Zhenyuan Yang, Zhengliang Liu, Ruidong Zhang, Yiheng Liu, Haiyang Sun, Yi Pan, Yiwei Li, Yifan Zhou, Hanqi Jiang, Junhao Chen, and Tianming Liu. 2024. Opportunities and Challenges of Large Language Models for Low-Resource Languages in Humanities Research. Preprint, arXiv:2412.04497. — [arXiv:2412.04497](https://arxiv.org/abs/2412.04497) find
  75. Hattie Zhou, Arwen Bradley, Etai Littwin, Noam Razin, Omid Saremi, Joshua M. Susskind, Samy Bengio, and Preetum Nakkiran. 2024. What Algorithms can Transformers Learn? A Study in Length Generalization. In The Twelfth International Conference on Learning Representations.
  76. Alex Warstadt, Yian Zhang, Xiaocheng Li, Haokun Liu, and Samuel R. Bowman. 2020b. Learning which features matter: RoBERTa acquires a preference for linguistic generalizations (eventually). In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 217–23… find
  77. A Proofs We make use of the following to establish that all languages we consider are context-sensitive. Proof. That 1-Dyck is context-free follows from the fact that it can be generated by the following context-free grammar: 𝑆 →(𝑆)𝑆, Lemma A.1. Any language definable in FO(M) can be recognized by a… find
  78. Proof. Mix Barrington et al. (1990) show that the class of languages definable in FO(M) is LOGTIME-uniform TC 0 , which is a subset of L=SPACE(log𝑛). On the other hand, the context-sensitive languages are those languages recognizable by linear-bounded automata (Kuroda, 1964). That is, CSL=NSPACE(𝑛).… find
  79. Therefore we can conclude that any language definable in FO(M) is context-sensitive. □ We will make use of the classical pumping lemma to establish that some specific languages considered are strictly context-sensitive, i.e., not context-free. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/hu-2025-between-circuits-chomsky-pre-pretraining/