On the Ability and Limitations of Transformers to Recognize Formal Languages
Open accessAbstract
Transformers have supplanted recurrent models in a large number of NLP tasks.However, the differences in their abilities to model different syntactic properties remain largely unknown.Past works suggest that LSTMs generalize very well on regular languages and have close connections with counter languages.In this work, we systematically study the ability of Transformers to model such languages as well as the role of its individual components in doing so.We first provide a construction of Transformers for a subclass of counter languages, including well-studied languages such as n-ary Boolean Expressions, Dyck-1, and its generalizations.In experiments, we find that Transformers do well on this subclass, and their learned mechanism strongly correlates with our construction.Perhaps surprisingly, in contrast to LSTMs, Transformers do well only on a subset of regular languages with degrading performance as we make languages more complex according to a well-known measure of complexity.Our analysis also provides insights on the role of self-attention mechanism in modeling certain behaviors and the influence of positional encoding schemes on the learning and generalization abilities of the model.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Models trained from scratch show little to no length generalization on parity.
“and parity (Bhattamishra et al., 2020;Chiang & Cholak, 2022;Ruoss et al., 2023;Delétang et al., 2023)”
From What Algorithms can Transformers Learn? A Study in Length Generalization (2023) · cites this paper as Bhattamishra et al., 2020
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, L., & Polosukhin, I. (2017) · arXiv · doi:10.48550/arxiv.1706.03762 · Cited by 120,404 · see citing works
Hochreiter, S., & Schmidhuber, J. (1997) · Neural Computation · doi:10.1162/neco.1997.9.8.1735 · Cited by 102,318 · see citing works
BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding
Devlin, J., Chang, M.-W., Lee, K., & Toutanova, K. (2019) · Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers) · doi:10.18653/v1/n19-1423 · Cited by 48,293 · see citing works
RoBERTa: A Robustly Optimized BERT Pretraining Approach
Liu, Y., Ott, M., Goyal, N., Du, J., Joshi, M., Chen, D., Levy, O., Lewis, M., Zettlemoyer, L., & Stoyanov, V. (2019) · arXiv · doi:10.48550/arxiv.1907.11692 · Cited by 16,515 · see citing works
Self-citationTransformer-XL: Attentive language models beyond a fixed-length context
Dai, Z., Yang, Z., Yang, Y., Carbonell, J., Le, Q., & Salakhutdinov, R. (2019) · Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics · doi:10.18653/v1/p19-1285 · Cited by 3,169 · see citing works
A primer in BERTology: What we know about how BERT works
Rogers, A., Kovaleva, O., & Rumshisky, A. (2020) · Transactions of the Association for Computational Linguistics · doi:10.1162/tacl_a_00349 · Cited by 1,552 · see citing works
Analyzing Multi-Head Self-Attention: Specialized Heads Do the Heavy Lifting, the Rest Can Be Pruned
Voita, E., Talbot, D., Moiseev, F., Sennrich, R., & Titov, I. (2019) · Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics · doi:10.18653/v1/p19-1580 · Cited by 1,146 · see citing works
DiSAN: Directional Self-Attention Network for RNN/CNN-Free Language Understanding
Shen, T., Zhou, T., Long, G., Jiang, J., Pan, S., & Zhang, C. (2018) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v32i1.11941 · Cited by 779 · see citing works
Finite Automata, Formal Logic, and Circuit Complexity
Howard Straubing, C. (1994) · Birkhäuser Boston eBooks · doi:10.1007/978-1-4612-0289-9 · Cited by 406 · see citing works
A Field Guide to Dynamical Recurrent Networks
Kolen, J. F., & Kremer, S. C. (2009) · Institute of Electrical and Electronics Engineers eBooks · doi:10.1109/9780470544037 · Cited by 338 · see citing works
Visualizing and Measuring the Geometry of BERTPreprint
Coenen, A., Reif, E., Yuan, A., Kim, B., Pearce, A., Viegas, F., & Wattenberg, M. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1906.02715 · Cited by 298 · see citing works
On the Practical Computational Power of Finite Precision RNNs for Language Recognition
Weiss, G., Goldberg, Y., & Yahav, E. (2018) · Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers) · doi:10.18653/v1/p18-2117 · Cited by 226 · see citing works
Formal language theory: refining the Chomsky hierarchy
Jäger, G., & Rogers, J. (2012) · Philosophical Transactions of the Royal Society B Biological Sciences · doi:10.1098/rstb.2012.0077 · Cited by 210 · see citing works
Counter machines and counter languages
Fischer, P. C., Meyer, A. R., & Rosenberg, A. L. (1968) · Theory of Computing Systems · doi:10.1007/bf01694011 · Cited by 207 · see citing works
On the Turing Completeness of Modern Neural Network ArchitecturesPreprint
Pérez, J., Marinkovic, J., & Barceló, P. (2019) · International Conference on Learning Representations · doi:10.48550/arxiv.1901.03429 · Cited by 187 · see citing works
Transformer Dissection: An Unified Understanding for Transformer’s Attention via the Lens of Kernel
Tsai, Y.-H. H., Bai, S., Yamada, M., Morency, L.-P., & Salakhutdinov, R. (2019) · Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP) · doi:10.18653/v1/d19-1443 · Cited by 173 · see citing works
Theoretical Limitations of Self-Attention in Neural Sequence Models
Hahn, M. (2020) · Transactions of the Association for Computational Linguistics · doi:10.1162/tacl_a_00306 · Cited by 165 · see citing works
Cohen, R., & Brzozowski, J. (1971) · Journal of Computer and System Sciences · doi:10.1016/s0022-0000(71)80003-x · Cited by 158 · see citing works
Are Transformers universal approximators of sequence-to-sequence functions?Preprint
Yun, C., Bhojanapalli, S., Rawat, A. S., Reddi, S. J., & Kumar, S. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1912.10077 · Cited by 149 · see citing works
Investigating BERT’s Knowledge of Language: Five Analysis Methods with NPIs
Warstadt, A., Cao, Y. H., Grosu, I., Peng, W., Blix, H., Nie, Y., Alsop, A., Bordia, S., Liu, H., Parrish, A., et al. (2019) · Conference on Empirical Methods in Natural Language Processing (EMNLP) · doi:10.18653/v1/d19-1286 · Cited by 100 · see citing works
Learning to Encode Position for Transformer with Continuous Dynamical ModelPreprint
Liu, X., Yu, H., Dhillon, I. S., & Hsieh, C. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2003.09229 · Cited by 98 · see citing works
First-order definable languages ∗
Diekert, V., & Gastin, P. B. (2008) · Cited by 94 · see citing works
A Formal Hierarchy of RNN Architectures
Merrill, W., Weiss, G. G., Goldberg, Y., Schwartz, R., Smith, N. A., & Yahav, E. (2020) · Proceedings of the conference - Association for Computational Linguistics. Meeting · doi:10.18653/v1/2020.acl-main.43 · Cited by 55 · see citing works
Sequential Neural Networks as Automata
Merrill, W. (2019) · Proceedings of the Workshop on Deep Learning and Formal Languages: Building Bridges · doi:10.18653/v1/w19-3901 · Cited by 54 · see citing works
Evaluating the Ability of LSTMs to Learn Context-Free Grammars
Sennhauser, L., & Berwick, R. C. (2018) · BlackboxNLP Workshop on Analyzing and Interpreting Neural Networks for NLP (BlackboxNLP) · doi:10.18653/v1/w18-5414 · Cited by 53 · see citing works
LSTM Networks Can Perform Dynamic Counting
Süzgün, M., Belinkov, Y., Shieber, S. M., & Gehrmann, S. (2019) · Proceedings of the Workshop on Deep Learning and Formal Languages: Building Bridges · doi:10.18653/v1/w19-3905 · Cited by 50 · see citing works
On the Computational Power of Transformers and Its Implications in Sequence Modeling
Bhattamishra, S., Patel, A., & Goyal, N. (2020) · Conference on Computational Natural Language Learning · doi:10.18653/v1/2020.conll-1.37 · Cited by 39 · see citing works
Self-citationAssessing the Ability of Self-Attention Networks to Learn Word Order
Yang, B., Wang, L., Wong, D. F., Chao, L. S., & Tu, Z. (2019) · Proceedings of the conference - Association for Computational Linguistics. Meeting · doi:10.18653/v1/p19-1354 · Cited by 35 · see citing works
On Evaluating the Generalization of LSTM Models in Formal LanguagesPreprint
Süzgün, M., Belinkov, Y., & Shieber, S. M. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1811.01001 · Cited by 30 · see citing works
The Dot-Depth Hierarchy, 45 Years Later
Pin, J.-É. (2017) · WORLD SCIENTIFIC eBooks · doi:10.1142/9789813148208_0008 · Cited by 28 · see citing works
Closing Brackets with Recurrent Neural Networks
Skachkova, N., Trost, T. A., & Klakow, D. (2018) · BlackboxNLP Workshop on Analyzing and Interpreting Neural Networks for NLP (BlackboxNLP) · doi:10.18653/v1/w18-5425 · Cited by 24 · see citing works
On the Computational Power of RNNsPreprint
Korsky, S., & Berwick, R. C. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1906.06349 · Cited by 24 · see citing works
Learning Deterministic Weighted Automata with Queries and CounterexamplesPreprint
Weiss, G., Goldberg, Y., & Yahav, E. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1910.13895 · Cited by 23 · see citing works
On the Linguistic Capacity of Real-Time Counter Automata
Merrill, W. (2020) · arXiv · doi:10.48550/arxiv.2004.06866 · Cited by 12 · see citing works
A Comparative Study of Rule Extraction for Recurrent Neural NetworksPreprint
Wang, Q., Zhang, K., Ororbia, A. G., Xing, X., Liu, X., & Giles, C. L. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1801.05420 · Cited by 8 · see citing works
Pretraining on Non-linguistic Structure as a Tool for Analyzing Learning Bias in Language ModelsPreprint
Papadimitriou, I., & Jurafsky, D. (2020) · arXiv (Cornell University) · Cited by 6 · see citing works
Flagged first, then by citations
Research works printed but not linked: 5
- Volker Diekert and Paul Gastin. 2008. First-order de- finable languages. In Logic and Automata: History and Perspectives [in Honor of Wolfgang Thomas], volume 2 of Texts in Logic and Games, pages 261- 306. Amsterdam University Press.
- Felix A Gers and E Schmidhuber. 2001. Lstm recur- rent networks learn simple context-free and context- sensitive languages. IEEE Transactions on Neural Networks, 12(6):1333-1340.
- Robert McNaughton and Seymour A. Papert. 1971. Counter-Free Automata (M.I.T. Research Mono- graph No. 65). The MIT Press.
- Joshua J. Michalenko, Ameesh Shah, Abhinav Verma, Swarat Chaudhuri, and Ankit B. Patel. 2019. Finite automata can be linearly decoded from language- recognizing RNNs. In International Conference on Learning Representations.
- Qinglong Wang, Kaixuan Zhang, II Ororbia, G Alexan- der, Xinyu Xing, Xue Liu, and C Lee Giles. 2018b. A comparative study of rule extraction for recurrent neural networks. arXiv preprint arXiv:1801.05420. · arXiv
Cited by
Sorted by citations
Beyond the Imitation Game: Quantifying and extrapolating the capabilities of language models
Srivastava, A., Rastogi, A., Rao, A., Shoeb, A. A. M., Abid, A., Fisch, A., Brown, A. R., Santoro, A., Gupta, A., Garriga-Alonso, A., et al. (2022) · arXiv · doi:10.48550/arxiv.2206.04615 · Cited by 569 · see citing works
Towards Revealing the Mystery behind Chain of Thought: a Theoretical Perspective
Feng, G., Zhang, B., Gu, Y., Ye, H., He, D., & Wang, L. (2023) · arXiv · doi:10.48550/arxiv.2305.15408 · Cited by 69 · see citing works
“[6] Satwik Bhattamishra, Kabir Ahuja, and Navin Goyal.”
BackgroundResultLinguistically inspired roadmap for building biologically reliable protein language models
Vu, M. H., Akbar, R., Robert, P. A., Świątczak, B., Sandve, G. K., Greiff, V., & Haug, D. T. T. (2023) · Nature Machine Intelligence · doi:10.1038/s42256-023-00637-1 · Cited by 57 · see citing works
Overcoming a Theoretical Limitation of Self-Attention
Chiang, D., & Cholak, P. (2022) · Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers) · doi:10.18653/v1/2022.acl-long.527 · Cited by 39 · see citing works
Formal Language Recognition by Hard Attention Transformers: Perspectives from Circuit Complexity
Hao, Y., Angluin, D., & Frank, R. (2022) · Transactions of the Association for Computational Linguistics · doi:10.1162/tacl_a_00490 · Cited by 27 · see citing works
What Formal Languages Can Transformers Express? A Survey
Strobl, L., Merrill, W., Weiss, G., Chiang, D., & Angluin, D. (2024) · Transactions of the Association for Computational Linguistics · doi:10.1162/tacl_a_00663 · Cited by 31 · see citing works
Saturated Transformers are Constant-Depth Threshold Circuits
Merrill, W., Sabharwal, A., & Smith, N. A. (2022) · Transactions of the Association for Computational Linguistics · doi:10.1162/tacl_a_00493 · Cited by 25 · see citing works
Randomized Positional Encodings Boost Length Generalization of Transformers
Ruoss, A., Delétang, G., Genewein, T., Grau-Moya, J., Csordás, R., Bennani, M., Legg, S., & Veness, J. (2023) · Proceedings of the conference - Association for Computational Linguistics. Meeting · doi:10.18653/v1/2023.acl-short.161 · Cited by 24 · see citing works
On the Transferability of Pre-trained Language Models: A Study from Artificial Datasets
Chiang, C.-H., & Lee, H.-Y. (2022) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v36i10.21295 · Cited by 18 · see citing works
Type-Constrained Code Generation with Language Models
Mündler-Sasahara, N., He, J.-X., Wang, H., Sen, K., Song, D., & Vechev, M. T. (2025) · Proc. ACM Program. Lang. · doi:10.1145/3729274 · Cited by 77 · see citing works
Effects of Parameter Norm Growth During Transformer Training: Inductive Bias from Gradient Descent
Merrill, W., Ramanujan, V., Goldberg, Y., Schwartz, R., & Smith, N. A. (2021) · Conference on Empirical Methods in Natural Language Processing (EMNLP) · doi:10.18653/v1/2021.emnlp-main.133 · Cited by 17 · see citing works
Characterizing In-Context Learning: When Can Transformers Match Standard Learning Algorithms?
Hawarey, M. (2026) · doi:10.65737/airmcs2026277 · Cited by 11 · see citing works
What Algorithms can Transformers Learn? A Study in Length Generalization
Zhou, H., Bradley, A., Littwin, E., Razin, N., Saremi, O., Susskind, J., Bengio, S., & Nakkiran, P. (2023) · arXiv · doi:10.48550/arxiv.2310.16028 · Cited by 10 · see citing works
“A number of papers have studied this question for specific classes of problems, such as decimal addition (Lee et al., 2023), Dyck-1 languages (Bhattamishra et al., 2020), Boolean functions (Abbe et al., 2023), structural recursion (Zhang et al., 2023), and finite state automaton (Liu et al., 2023).”
BackgroundUtility-Based Route Choice Behavior Modeling Using Deep Sequential Models
Dong, G., Kweon, Y., Park, B., & Boukhechba, M. (2022) · Journal of Big Data Analytics in Transportation · doi:10.1007/s42421-022-00058-3 · Cited by 10 · see citing works
Simplicity Bias in Transformers and their Ability to Learn Sparse Boolean Functions
Bhattamishra, S., Patel, A., Kanade, V., & Blunsom, P. (2023) · Proceedings of the conference - Association for Computational Linguistics. Meeting · doi:10.18653/v1/2023.acl-long.317 · Cited by 10 · see citing works
Self-citationProvably Learning a Multi-head Attention Layer
Chen, S., & Li, Y. (2025) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3717823.3718174 · Cited by 6 · see citing works
Do Transformers Parse while Predicting the Masked Word?
Zhao, H., Panigrahi, A., Ge, R., & Arora, S. (2023) · Conference on Empirical Methods in Natural Language Processing (EMNLP) · doi:10.18653/v1/2023.emnlp-main.1029 · Cited by 6 · see citing works
What do Large Language Models Learn beyond Language?
Madasu, A., & Srivastava, S. (2022) · Findings of the Association for Computational Linguistics: EMNLP (Findings of EMNLP) · doi:10.18653/v1/2022.findings-emnlp.516 · Cited by 6 · see citing works
Why are Sensitive Functions Hard for Transformers?
Hahn, M., & Rofin, M. (2024) · arXiv · doi:10.48550/arxiv.2402.09963 · Cited by 6
Linguistics-based formalization of the antibody language as a basis for antibody language models
Vu, M. H., Robert, P. A., Akbar, R., Świątczak, B., Sandve, G. K., Haug, D. T. T., & Greiff, V. (2024) · Nature Computational Science · doi:10.1038/s43588-024-00642-3 · Cited by 15 · see citing works
On the Practical Ability of Recurrent Neural Networks to Recognize Hierarchical Languages
Bhattamishra, S., Ahuja, K., & Goyal, N. (2020) · International Conference on Computational Linguistics · doi:10.18653/v1/2020.coling-main.129 · Cited by 5 · see citing works
Self-citationRethinking Transformers for Efficiency and ScalabilityPreprint
Huang, J., & Bao, Y. (2025) · SSRN Electronic Journal · doi:10.2139/ssrn.5161897 · Cited by 5 · see citing works
MultiFix: Learning to Repair Multiple Errors by Optimal Alignment Learning
Seo, H., Han, Y.-S., & Ko, S. (2021) · Findings of the Association for Computational Linguistics: EMNLP (Findings of EMNLP) · doi:10.18653/v1/2021.findings-emnlp.417 · Cited by 4 · see citing works
Evaluating Transformer’s Ability to Learn Mildly Context-Sensitive Languages
Wang, S., & Steinert‐Threlkeld, S. (2023) · BlackboxNLP Workshop on Analyzing and Interpreting Neural Networks for NLP (BlackboxNLP) · doi:10.18653/v1/2023.blackboxnlp-1.21 · Cited by 3 · see citing works
Irie, K., Csordás, R., & Schmidhuber, J. (2023) · Conference on Empirical Methods in Natural Language Processing (EMNLP) · doi:10.18653/v1/2023.emnlp-main.588 · Cited by 3 · see citing works
Guan, B., & Gu, X. (2026) · Big Data Research · doi:10.1016/j.bdr.2025.100588 · Cited by 2 · see citing works
Can adversarial attacks by large language models be attributed?
Cebrián, M., Abeliuk, A., & Telle, J. A. (2026) · PLOS complex systems. · doi:10.1371/journal.pcsy.0000085 · Cited by 2 · see citing works
Generating simulated data with a large language model
Kerley, J., Anderson, D. T., Buck, A. R., & Alvey, B. J. (2024) · Synthetic Data for Artificial Intelligence and Machine Learning: Tools, Techniques, and Applications · doi:10.1117/12.3013460 · Cited by 2 · see citing works
Implicit n-grams Induced by Recurrence
Sun, X., & Lu, W. (2022) · Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (NAACL-HLT) · doi:10.18653/v1/2022.naacl-main.117 · Cited by 2 · see citing works
Can the Transformer Learn Nested Recursion with Symbol Masking?
Bernardy, J.-P., Ek, A., & Maraev, V. (2021) · Findings of the Association for Computational Linguistics: ACL (Findings of ACL) · doi:10.18653/v1/2021.findings-acl.67 · Cited by 2 · see citing works
Chi, T.-C., Fan, T.-H., Rudnicky, A. I., & Ramadge, P. J. (2023) · Findings of the Association for Computational Linguistics: EMNLP (Findings of EMNLP) · doi:10.18653/v1/2023.findings-emnlp.397 · Cited by 1 · see citing works
Grebenkin, D., & Bondarenko, I. (2024) · Journal of Mathematical Sciences · doi:10.1007/s10958-024-07420-6 · Cited by 1 · see citing works
Formal Languages and the NLP Black Box
Merrill, W. (2023) · Lecture notes in computer science · doi:10.1007/978-3-031-33264-7_1 · Cited by 1 · see citing works
Nikolaev, D., & Padó, S. (2023) · BlackboxNLP Workshop on Analyzing and Interpreting Neural Networks for NLP (BlackboxNLP) · doi:10.18653/v1/2023.blackboxnlp-1.11 · Cited by 4 · see citing works
Bueno, M. C., Gemmell, C., Dalton, J., Lotufo, R., & Nogueira, R. F. (2022) · Workshop on Mathematical Natural Language Processing (MathNLP) · doi:10.18653/v1/2022.mathnlp-1.3 · Cited by 1 · see citing works
Learning and Generalization in RNNsPreprint
Panigrahi, A., & Goyal, N. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2106.00047 · Cited by 1 · see citing works
Self-citationOn the Power of Saturated Transformers: A View from Circuit Complexity.Preprint
Merrill, W., Goldberg, Y., Schwartz, R., & Smith, N. A. (2021) · arXiv (Cornell University) · Cited by 1 · see citing works
Training dynamics of neural language models
Saphra, N. (2021) · ERA · doi:10.7488/era/1421 · Cited by 1 · see citing works
Implicit Language Models are RNNs: Balancing Parallelization and Expressivity
Schöne, M., Rahmani, B., Kremer, H., Falck, F., Ballani, H., & Gladrow, J. (2025) · arXiv · doi:10.48550/arxiv.2502.07827
Formal Languages, Deep Learning, Topology and AlgebraicWord Problems
Ackerman, J., & Cybenko, G. V. (2021) · IEEE Security and Privacy Workshops (SPW) · doi:10.1109/spw53761.2021.00027
Abstraction, Reasoning and Deep Learning: A Study of the "Look and Say" Sequence
Zadrozny, W. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2109.12755
Pushdown Layers: Encoding Recursive Structure in Transformer Language Models
Murty, S., Sharma, P., Andreas, J., & Manning, C. D. (2023) · Conference on Empirical Methods in Natural Language Processing (EMNLP) · doi:10.18653/v1/2023.emnlp-main.195 · Cited by 2 · see citing works
Unraveling Feature Extraction Mechanisms in Neural Networks
Sun, X., Li, J., & Lü, W. (2023) · Conference on Empirical Methods in Natural Language Processing (EMNLP) · doi:10.18653/v1/2023.emnlp-main.650
Extracting Moore Machines from Transformers Using Queries and Counterexamples
Adriaensen, R., & Maene, J. (2025) · Lecture notes in computer science · doi:10.1007/978-3-031-91398-3_31 · Cited by 1 · see citing works
Learning and Generalization of Vision Transformers
Chen, P., & Liu, S. (2025) · Springer eBooks · doi:10.1007/978-3-031-76770-8_3
Mitros, J. (2025) · Lecture notes in computer science · doi:10.1007/978-3-032-04558-4_14
Hayakawa, D. (2025) · Journal of Natural Language Processing · doi:10.5715/jnlp.32.1310
Three Tiers of Computation in Transformers and in Brain Architectures
Graham, E., & Granger, R. (2026) · ACM Transactions on Intelligent Systems and Technology · doi:10.1145/3844612
A Theoretical Framework Bridging Attention and SVM Optimization Dynamics and Sparsity
Li, Z., Song, Z., & Zhao, J. (2025) · IEEE International Conference on Big Data (BigData) · doi:10.1109/bigdata66926.2025.11402021
Study of the abstraction capabilities of neural language models
Li, B. (2023) · theses.fr (ABES) · doi:10.70675/0236e084zee1ez4013z8f5bz6eebee3f0e4e
Intelligibility of Recurrent Neural Networks via Finite State Machines
Marzouk, M. R. (2024) · theses.fr (ABES) · doi:10.70675/67c57743zf027z4a51zbd70zddd2e546358f
A Computational Analysis of AI Models in Recognizing Formal Languages
Hussain, S., Bai, A., Kumari, P., Kumar, K., Salman, A., Rasheed, K., & Yazdani, S. S. (2026) · International Journal of Innovations in Science and Technology · doi:10.33411/ijist/ojs1775
Type-Constrained Code Generation with Language Models
Mündler, N., He, J., Wang, H., Sen, K., Song, D., & Vechev, M. (2025) · arXiv · doi:10.48550/arxiv.2504.09246
- Authors
- Bhattamishra, S., Ahuja, K., & Goyal, N.
- Affiliations
- Microsoft (United States) (US)
- Microsoft Research (India) (IN)
- Venue
- Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)
- Published
- 2020
- Pages
- 7096-7116
- OpenAlex
- W3091917188
- Cited by
- 48
- References
- 34
- Citations by year
- 2026: 5 · 2025: 8 · 2024: 5 · 2023: 12 · 2022: 9 · 2021: 8 · 2020: 1
- FWCI
- 8.07
- Type
- conference paper
- Language
- en
- Open access
- hybrid
- doi.org
- Licence
- cc-by
- Locations
- Conference on Empirical Methods in Natural Language Processing (EMNLP) (publishedVersion, cc-by)
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- Funders
- Microsoft Research
- Topics
- Physical Sciences › Computer Science › Computational Theory and Mathematics › semigroups and automata theory
- Physical Sciences › Computer Science › Artificial Intelligence › Natural Language Processing Techniques
- Physical Sciences › Computer Science › Artificial Intelligence › Topic Modeling
- Keywords
- transformer models, formal language recognition, regular languages, self-attention, positional encoding, LSTM comparison, syntactic complexity
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
