---
title: "On the Ability and Limitations of Transformers to Recognize"
description: "This EMNLP 2020 study asks which formal languages Transformers can actually learn in practice… 41 references, cited by 61 papers here."
authors: ["Satwik Bhattamishra", "Kabir Ahuja", "Navin Goyal"]
year: 2020
venue: "Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)"
source: "https://aclanthology.org/2020.emnlp-main.576/"
doi: "10.18653/v1/2020.emnlp-main.576"
arxiv: "2009.11264"
licence: "CC BY 4.0 (ACL Anthology)"
licence_url: "https://creativecommons.org/licenses/by/4.0/"
summary_licence: "Elamur Cosmic License"
canonical: "https://research.elamur.ai/free/en/papers/bhattamishra-2020-ability-limitations-transformers-recognize-formal/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/bhattamishra-2020-ability-limitations-transformers-recognize-formal/)

[home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [2020](https://md.research.elamur.ai/free/en/papers/2020/page/5/) / On the Ability and Limitations of Transformers to Recognize Formal Languages

# On the Ability and Limitations of Transformers to Recognize Formal Languages

**Authors:** [Satwik Bhattamishra](https://md.research.elamur.ai/free/en/authors/satwik-bhattamishra/), [Kabir Ahuja](https://md.research.elamur.ai/free/en/authors/kabir-ahuja/) and [Navin Goyal](https://md.research.elamur.ai/free/en/authors/navin-goyal/) · **Year:** 2020 · **Venue:** [Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)](https://md.research.elamur.ai/free/en/venues/emnlp/) ([EMNLP 2020](https://md.research.elamur.ai/free/en/venues/emnlp/2020/)) · **Publisher:** [Association for Computational Linguistics](https://md.research.elamur.ai/free/en/publishers/association-for-computational-linguistics/) · **Licence:** [CC BY 4.0 (ACL Anthology)](https://creativecommons.org/licenses/by/4.0/)

**Links:** [Publisher's page](https://aclanthology.org/2020.emnlp-main.576/) · [PDF](https://aclanthology.org/2020.emnlp-main.576.pdf) · [DOI 10.18653/v1/2020.emnlp-main.576](https://doi.org/10.18653/v1/2020.emnlp-main.576) · [arXiv 2009.11264](https://arxiv.org/abs/2009.11264) · [OpenAlex](https://openalex.org/W3091917188)

**Citations:** 48 citations (OpenAlex, 2026-10-14) · [61](https://md.research.elamur.ai/free/en/papers/bhattamishra-2020-ability-limitations-transformers-recognize-formal/cited-by/) in our library, of the 141,840 papers whose bibliographies we read

## Summary
This EMNLP 2020 study asks which formal languages Transformers can actually learn in practice, compared with LSTMs. LSTMs are already known to handle regular languages and to behave like counter automata. The authors first give a theoretical construction showing that self-attention can indirectly emulate counter operations. This lets an encoder-only Transformer (BERT/GPT-style, with positional masking) recognize a subclass of counter languages, including Dyck-1, Shuffle-Dyck and n-ary Boolean Expressions. They then train models on more than 25 carefully chosen formal languages. They test generalization to longer strings, visualize internal representations, and vary positional encodings and depth.

On the counter subclass, Transformers generalize well, and their learned representations track the proposed construction. On regular languages, however, they lag clearly behind LSTMs. Performance drops on languages requiring periodicity or modular counting, and on star-free languages of higher dot-depth. This matters because it exposes concrete weaknesses of self-attention on inputs of practical size. It also highlights how much the architecture depends on positional encoding.

## Key points
- **Coverage:** over 25 formal languages in total, including over 15 regular ones. Counter languages tested include Dyck-1, Shuffle-k (Shuffle-Dyck), BoolExp-n, aⁿbⁿ and aⁿbⁿcⁿ.
- **Regular languages:** results fit the hypothesis that Transformers handle star-free languages of dot-depth 1. They struggle with higher dot-depths and with non-star-free languages.
- **Need for positional encoding:** without positional encoding, softmax aggregation makes outputs identical on runs of a single symbol. Such a model therefore provably cannot recognize (aa)* or even short Parity strings, whatever its size.
- **Custom encodings:** a cos(nπ) positional encoding solves (aa)* but fails on (aaaa)*. Trainable fixed-length embeddings learned a cos(nπ)-like pattern but cannot extrapolate to longer inputs.
- **Relation to prior theory:** the work contrasts with Hahn (2020), whose impossibility results for Parity and Dyck-2 concern very long inputs and expressivity only. Here the focus is on learnability at practical lengths.

*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

- [Microsoft](https://md.research.elamur.ai/free/en/companies/microsoft/) — Company, Redmond, United States · 240 works · 123,537 citations
- [Microsoft Research](https://md.research.elamur.ai/free/en/companies/microsoft-research/) — Company, Bengaluru, India · 9 works · 3,523 citations

📚 Shelves (5): [🖥️ Computer Science](https://md.research.elamur.ai/free/en/shelves/computer-science/) · 9,086 works · [🤖 Artificial Intelligence](https://md.research.elamur.ai/free/en/shelves/computer-science/artificial-intelligence/) · 8,889 works · [🎭 Arts and Humanities](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/) · 9,296 works · [🗣️ Language and Linguistics](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/language-and-linguistics/) · 9,206 works · [🧮 Computational Theory and Mathematics](https://md.research.elamur.ai/free/en/shelves/computer-science/computational-theory-and-mathematics/) · 116 works

## Cite

Cite as: Satwik Bhattamishra, Kabir Ahuja and Navin Goyal. 2020. On the Ability and Limitations of Transformers to Recognize Formal Languages. Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP).

The paper itself, not this page. BibTeX from the library's record of the work.

```bibtex
@inproceedings{bhattamishra2020ability,
  title = {{On the Ability and Limitations of Transformers to Recognize Formal Languages}},
  author = {Satwik Bhattamishra, Kabir Ahuja and Navin Goyal},
  booktitle = {Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)},
  year = {2020},
  doi = {10.18653/v1/2020.emnlp-main.576},
  eprint = {2009.11264},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.18653/v1/2020.emnlp-main.576}
}
```

- [← previous Lexically Constrained Neural Machine Translation with Levenshtein Transformer](https://md.research.elamur.ai/free/en/papers/susanto-2020-lexically-constrained-neural-machine-translation/)
- [next → Overview of OSACT4 Arabic Offensive Language Detection Shared Task](https://md.research.elamur.ai/free/en/papers/mubarak-2020-overview-osact4-arabic-offensive-language/)
- [↑ back to papers of 2020](https://md.research.elamur.ai/free/en/papers/2020/page/5/)

## References

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

1. Satwik Bhattamishra, Arkil Patel, and Navin Goyal. 2020. On the computational power of transformers and its implications in sequence modeling. arXiv preprint arXiv:2006.09286. [find](https://scholar.google.com/scholar?q=Satwik+Bhattamishra%2C+Arkil+Patel%2C+and+Navin+Goyal%2E+2020%2E+On+the+computational+power+of+transformers+and+its+implications+in+sequence+modeling%2E+arXiv+preprint+arXiv%3A2006%2E09286%2E)
2. Rina Cohen and Janusz Brzozowski. 1971. Dot-depth of star-free events. Journal of Computer and System Sciences, 5:1–16. [find](https://scholar.google.com/scholar?q=Rina+Cohen+and+Janusz+Brzozowski%2E+1971%2E+Dot%2Ddepth+of+star%2Dfree+events%2E+Journal+of+Computer+and+System+Sciences%2C+5%3A1%E2%80%9316%2E)
3. Zihang Dai, Zhilin Yang, Yiming Yang, Jaime Carbonell, Quoc Le, and Ruslan Salakhutdinov. 2019. Transformer-XL: Attentive language models beyond a fixed-length context. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 2978–2988, Florence, Italy. Assoc… [find](https://scholar.google.com/scholar?q=Zihang+Dai%2C+Zhilin+Yang%2C+Yiming+Yang%2C+Jaime+Carbonell%2C+Quoc+Le%2C+and+Ruslan+Salakhutdinov%2E+2019%2E+Transformer%2DXL%3A+Attentive+language+models+beyond+a+fixed%2Dlength+context%2E+In+Proceedings+of+the+57th+Annu)
4. Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019. [BERT: Pre-training of deep bidirectional transformers for language understanding](https://md.research.elamur.ai/free/en/papers/devlin-2019-bert-pre-training-deep-bidirectional/). In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies,…
5. Volker Diekert and Paul Gastin. 2008. First-order definable 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. [find](https://scholar.google.com/scholar?q=Volker+Diekert+and+Paul+Gastin%2E+2008%2E+First%2Dorder+definable+languages%2E+In+Logic+and+Automata%3A+History+and+Perspectives+%5Bin+Honor+of+Wolfgang+Thomas%5D%2C+volume+2+of+Texts+in+Logic+and+Games%2C+pages+261%E2%80%93+3)
6. Patrick C Fischer, Albert R Meyer, and Arnold L Rosenberg. 1968. Counter machines and counter languages. Mathematical systems theory, 2(3):265– 283. [find](https://scholar.google.com/scholar?q=Patrick+C+Fischer%2C+Albert+R+Meyer%2C+and+Arnold+L+Rosenberg%2E+1968%2E+Counter+machines+and+counter+languages%2E+Mathematical+systems+theory%2C+2%283%29%3A265%E2%80%93+283%2E)
7. Isabel Papadimitriou and Dan Jurafsky. 2020. Pretraining on non-linguistic structure as a tool for analyzing learning bias in language models. arXiv preprint arXiv:2004.14601. — [arXiv:2004.14601](https://arxiv.org/abs/2004.14601) [find](https://scholar.google.com/scholar?q=Isabel+Papadimitriou+and+Dan+Jurafsky%2E+2020%2E+Pretraining+on+non%2Dlinguistic+structure+as+a+tool+for+analyzing+learning+bias+in+language+models%2E+arXiv+preprint+arXiv%3A2004%2E14601%2E+%E2%80%94+%5BarXiv%3A2004%2E14601%5D%28htt)
8. Felix A Gers and E Schmidhuber. 2001. Lstm recurrent networks learn simple context-free and context-sensitive languages. IEEE Transactions on Neural Networks, 12(6):1333–1340. [find](https://scholar.google.com/scholar?q=Felix+A+Gers+and+E+Schmidhuber%2E+2001%2E+Lstm+recurrent+networks+learn+simple+context%2Dfree+and+context%2Dsensitive+languages%2E+IEEE+Transactions+on+Neural+Networks%2C+12%286%29%3A1333%E2%80%931340%2E)
9. Jorge Pérez, Javier Marinković, and Pablo Barceló. 2019. On the turing completeness of modern neural network architectures. In International Conference on Learning Representations. [find](https://scholar.google.com/scholar?q=Jorge+Pe%CC%81rez%2C+Javier+Marinkovic%CC%81%2C+and+Pablo+Barcelo%CC%81%2E+2019%2E+On+the+turing+completeness+of+modern+neural+network+architectures%2E+In+International+Conference+on+Learning+Representations%2E)
10. Michael Hahn. 2020. Theoretical limitations of self-attention in neural sequence models. Transactions of the Association for Computational Linguistics, 8:156–171. [find](https://scholar.google.com/scholar?q=Michael+Hahn%2E+2020%2E+Theoretical+limitations+of+self%2Dattention+in+neural+sequence+models%2E+Transactions+of+the+Association+for+Computational+Linguistics%2C+8%3A156%E2%80%93171%2E)
11. Jean-ric Pin. 2017. The dot-depth hierarchy, 45 years later. In The Role of Theory in Computer Science, pages 177–201. [find](https://scholar.google.com/scholar?q=Jean%2Dric+Pin%2E+2017%2E+The+dot%2Ddepth+hierarchy%2C+45+years+later%2E+In+The+Role+of+Theory+in+Computer+Science%2C+pages+177%E2%80%93201%2E)
12. Sepp Hochreiter and Jürgen Schmidhuber. 1997. Long short-term memory. Neural computation, 9(8):1735–1780. [find](https://scholar.google.com/scholar?q=Sepp+Hochreiter+and+Ju%CC%88rgen+Schmidhuber%2E+1997%2E+Long+short%2Dterm+memory%2E+Neural+computation%2C+9%288%29%3A1735%E2%80%931780%2E)
13. Gerhard Jäger and James Rogers. 2012. Formal language theory: refining the chomsky hierarchy. Philosophical Transactions of the Royal Society B: Biological Sciences, 367(1598):1956–1970. [find](https://scholar.google.com/scholar?q=Gerhard+Ja%CC%88ger+and+James+Rogers%2E+2012%2E+Formal+language+theory%3A+refining+the+chomsky+hierarchy%2E+Philosophical+Transactions+of+the+Royal+Society+B%3A+Biological+Sciences%2C+367%281598%29%3A1956%E2%80%931970%2E)
14. John F Kolen and Stefan C Kremer. 2001. A field guide to dynamical recurrent networks. John Wiley & Sons. [find](https://scholar.google.com/scholar?q=John+F+Kolen+and+Stefan+C+Kremer%2E+2001%2E+A+field+guide+to+dynamical+recurrent+networks%2E+John+Wiley+%26+Sons%2E)
15. Samuel A Korsky and Robert C Berwick. 2019. On the computational power of rnns. arXiv preprint arXiv:1906.06349. — [arXiv:1906.06349](https://arxiv.org/abs/1906.06349) [find](https://scholar.google.com/scholar?q=Samuel+A+Korsky+and+Robert+C+Berwick%2E+2019%2E+On+the+computational+power+of+rnns%2E+arXiv+preprint+arXiv%3A1906%2E06349%2E+%E2%80%94+%5BarXiv%3A1906%2E06349%5D%28https%3A%2F%2Farxiv%2Eorg%2Fabs%2F1906%2E06349%29)
16. Xuanqing Liu, Hsiang-Fu Yu, Inderjit Dhillon, and Cho-Jui Hsieh. 2020. Learning to encode position for transformer with continuous dynamical model. arXiv preprint arXiv:2003.09229. — [arXiv:2003.09229](https://arxiv.org/abs/2003.09229) [find](https://scholar.google.com/scholar?q=Xuanqing+Liu%2C+Hsiang%2DFu+Yu%2C+Inderjit+Dhillon%2C+and+Cho%2DJui+Hsieh%2E+2020%2E+Learning+to+encode+position+for+transformer+with+continuous+dynamical+model%2E+arXiv+preprint+arXiv%3A2003%2E09229%2E+%E2%80%94+%5BarXiv%3A2003%2E09229)
17. Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. 2019. Roberta: A robustly optimized bert pretraining approach. arXiv preprint arXiv:1907.11692. [find](https://scholar.google.com/scholar?q=Yinhan+Liu%2C+Myle+Ott%2C+Naman+Goyal%2C+Jingfei+Du%2C+Mandar+Joshi%2C+Danqi+Chen%2C+Omer+Levy%2C+Mike+Lewis%2C+Luke+Zettlemoyer%2C+and+Veselin+Stoyanov%2E+2019%2E+Roberta%3A+A+robustly+optimized+bert+pretraining+approach%2E+a)
18. Robert McNaughton and Seymour A. Papert. 1971. Counter-Free Automata (M.I.T. Research Monograph No. 65). The MIT Press. [find](https://scholar.google.com/scholar?q=Robert+McNaughton+and+Seymour+A%2E+Papert%2E+1971%2E+Counter%2DFree+Automata+%28M%2EI%2ET%2E+Research+Monograph+No%2E+65%29%2E+The+MIT+Press%2E)
19. William Merrill. 2019. Sequential neural networks as automata. In Proceedings of the Workshop on Deep Learning and Formal Languages: Building Bridges, pages 1–13, Florence. Association for Computational Linguistics. [find](https://scholar.google.com/scholar?q=William+Merrill%2E+2019%2E+Sequential+neural+networks+as+automata%2E+In+Proceedings+of+the+Workshop+on+Deep+Learning+and+Formal+Languages%3A+Building+Bridges%2C+pages+1%E2%80%9313%2C+Florence%2E+Association+for+Computation)
20. William Merrill. 2020. On the linguistic capacity of real-time counter automata. arXiv preprint arXiv:2004.06866. — [arXiv:2004.06866](https://arxiv.org/abs/2004.06866) [find](https://scholar.google.com/scholar?q=William+Merrill%2E+2020%2E+On+the+linguistic+capacity+of+real%2Dtime+counter+automata%2E+arXiv+preprint+arXiv%3A2004%2E06866%2E+%E2%80%94+%5BarXiv%3A2004%2E06866%5D%28https%3A%2F%2Farxiv%2Eorg%2Fabs%2F2004%2E06866%29)
21. Alec Radford, Karthik Narasimhan, Tim Salimans, and Ilya Sutskever. 2018. Improving language understanding by generative pre-training. URL [https://s3-us-west-2.amazonaws](https://s3-us-west-2.amazonaws). com/openai-assets/researchcovers/languageunsupervised/language understanding paper. pdf. [↗](https://s3-us-west-2.amazonaws)
22. Emily Reif, Ann Yuan, Martin Wattenberg, Fernanda B Viegas, Andy Coenen, Adam Pearce, and Been Kim. 2019. [Visualizing and measuring the geometry of bert](https://md.research.elamur.ai/free/en/papers/coenen-2019-visualizing-measuring-geometry-bert/). In Advances in Neural Information Processing Systems, pages 8592–8600.
23. Anna Rogers, Olga Kovaleva, and Anna Rumshisky. 2020. [A primer in bertology: What we know about how bert works](https://md.research.elamur.ai/free/en/papers/rogers-2020-primer-bertology-what-we-know/). arXiv preprint arXiv:2002.12327.
24. Luzi Sennhauser and Robert Berwick. 2018. Evaluating the ability of LSTMs to learn context-free grammars. In Proceedings of the 2018 EMNLP Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP, pages 115–124, Brussels, Belgium. Association for Computational Linguistics. [find](https://scholar.google.com/scholar?q=Luzi+Sennhauser+and+Robert+Berwick%2E+2018%2E+Evaluating+the+ability+of+LSTMs+to+learn+context%2Dfree+grammars%2E+In+Proceedings+of+the+2018+EMNLP+Workshop+BlackboxNLP%3A+Analyzing+and+Interpreting+Neural+Netwo)
25. Tao Shen, Tianyi Zhou, Guodong Long, Jing Jiang, Shirui Pan, and C. Zhang. 2018. Disan: Directional self-attention network for rnn/cnn-free language understanding. In AAAI. [find](https://scholar.google.com/scholar?q=Tao+Shen%2C+Tianyi+Zhou%2C+Guodong+Long%2C+Jing+Jiang%2C+Shirui+Pan%2C+and+C%2E+Zhang%2E+2018%2E+Disan%3A+Directional+self%2Dattention+network+for+rnn%2Fcnn%2Dfree+language+understanding%2E+In+AAAI%2E)
26. Natalia Skachkova, Thomas Trost, and Dietrich Klakow. 2018. Closing brackets with recurrent neural networks. In Proceedings of the 2018 EMNLP Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP, pages 232–239, Brussels, Belgium. Association for Computational Linguistics. [find](https://scholar.google.com/scholar?q=Natalia+Skachkova%2C+Thomas+Trost%2C+and+Dietrich+Klakow%2E+2018%2E+Closing+brackets+with+recurrent+neural+networks%2E+In+Proceedings+of+the+2018+EMNLP+Workshop+BlackboxNLP%3A+Analyzing+and+Interpreting+Neural+Ne)
27. Howard Straubing. 1994. Finite Automata, Formal Logic, and Circuit Complexity. Birkhauser Verlag, CHE. [find](https://scholar.google.com/scholar?q=Howard+Straubing%2E+1994%2E+Finite+Automata%2C+Formal+Logic%2C+and+Circuit+Complexity%2E+Birkhauser+Verlag%2C+CHE%2E)
28. William Merrill, Gail Weiss, Yoav Goldberg, Roy Schwartz, Noah A Smith, and Eran Yahav. 2020. A formal hierarchy of rnn architectures. arXiv preprint arXiv:2004.08500. [find](https://scholar.google.com/scholar?q=William+Merrill%2C+Gail+Weiss%2C+Yoav+Goldberg%2C+Roy+Schwartz%2C+Noah+A+Smith%2C+and+Eran+Yahav%2E+2020%2E+A+formal+hierarchy+of+rnn+architectures%2E+arXiv+preprint+arXiv%3A2004%2E08500%2E)
29. Mirac Suzgun, Yonatan Belinkov, Stuart Shieber, and Sebastian Gehrmann. 2019a. 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. [find](https://scholar.google.com/scholar?q=Mirac+Suzgun%2C+Yonatan+Belinkov%2C+Stuart+Shieber%2C+and+Sebastian+Gehrmann%2E+2019a%2E+LSTM+networks+can+perform+dynamic+counting%2E+In+Proceedings+of+the+Workshop+on+Deep+Learning+and+Formal+Languages%3A+Buildin)
30. 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. [find](https://scholar.google.com/scholar?q=Joshua+J%2E+Michalenko%2C+Ameesh+Shah%2C+Abhinav+Verma%2C+Swarat+Chaudhuri%2C+and+Ankit+B%2E+Patel%2E+2019%2E+Finite+automata+can+be+linearly+decoded+from+language%2Drecognizing+RNNs%2E+In+International+Conference+on+Lea)
31. Mirac Suzgun, Yonatan Belinkov, and Stuart M. Shieber. 2019b. On evaluating the generalization of LSTM models in formal languages. In Proceedings of the Society for Computation in Linguistics (SCiL) 2019, pages 277–286. [find](https://scholar.google.com/scholar?q=Mirac+Suzgun%2C+Yonatan+Belinkov%2C+and+Stuart+M%2E+Shieber%2E+2019b%2E+On+evaluating+the+generalization+of+LSTM+models+in+formal+languages%2E+In+Proceedings+of+the+Society+for+Computation+in+Linguistics+%28SCiL%29+2)
32. Yao-Hung Hubert Tsai, Shaojie Bai, Makoto Yamada, Louis-Philippe Morency, and Ruslan Salakhutdinov. 2019. Transformer dissection: An unified understanding for transformer’s attention via the lens of kernel. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and… [find](https://scholar.google.com/scholar?q=Yao%2DHung+Hubert+Tsai%2C+Shaojie+Bai%2C+Makoto+Yamada%2C+Louis%2DPhilippe+Morency%2C+and+Ruslan+Salakhutdinov%2E+2019%2E+Transformer+dissection%3A+An+unified+understanding+for+transformer%E2%80%99s+attention+via+the+lens+of+k)
33. Chulhee Yun, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank Reddi, and Sanjiv Kumar. 2020. Are transformers universal approximators of sequence-to-sequence functions? In International Conference on Learning Representations. [find](https://scholar.google.com/scholar?q=Chulhee+Yun%2C+Srinadh+Bhojanapalli%2C+Ankit+Singh+Rawat%2C+Sashank+Reddi%2C+and+Sanjiv+Kumar%2E+2020%2E+Are+transformers+universal+approximators+of+sequence%2Dto%2Dsequence+functions%3F+In+International+Conference+on+)
34. Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. 2017. [Attention is all you need](https://md.research.elamur.ai/free/en/papers/vaswani-2017-attention-all-need/). In Advances in neural information processing systems, pages 5998–6008.
35. Elena Voita, David Talbot, Fedor Moiseev, Rico Sennrich, and Ivan Titov. 2019. [Analyzing multi-head self-attention: Specialized heads do the heavy lifting, the rest can be pruned](https://md.research.elamur.ai/free/en/papers/voita-2019-analyzing-multi-head-self-attention/). In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 5797–5808, Florence, I…
36. Qinglong Wang, Kaixuan Zhang, Alexander G. Ororbia II, Xinyu Xing, Xue Liu, and C. Lee Giles. 2018a. A comparative study of rule extraction for recurrent neural networks. CoRR, abs/1801.05420v2. — [arXiv:1801.05420](https://arxiv.org/abs/1801.05420) [find](https://scholar.google.com/scholar?q=Qinglong+Wang%2C+Kaixuan+Zhang%2C+Alexander+G%2E+Ororbia+II%2C+Xinyu+Xing%2C+Xue+Liu%2C+and+C%2E+Lee+Giles%2E+2018a%2E+A+comparative+study+of+rule+extraction+for+recurrent+neural+networks%2E+CoRR%2C+abs%2F1801%2E05420v2%2E+%E2%80%94+%5Bar)
37. Qinglong Wang, Kaixuan Zhang, II Ororbia, G Alexander, 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:1801.05420](https://arxiv.org/abs/1801.05420) [find](https://scholar.google.com/scholar?q=Qinglong+Wang%2C+Kaixuan+Zhang%2C+II+Ororbia%2C+G+Alexander%2C+Xinyu+Xing%2C+Xue+Liu%2C+and+C+Lee+Giles%2E+2018b%2E+A+comparative+study+of+rule+extraction+for+recurrent+neural+networks%2E+arXiv+preprint+arXiv%3A1801%2E0542)
38. Alex Warstadt, Yu Cao, Ioana Grosu, Wei Peng, Hagen Blix, Yining Nie, Anna Alsop, Shikha Bordia, Haokun Liu, Alicia Parrish, Sheng-Fu Wang, Jason Phang, Anhad Mohananey, Phu Mon Htut, Paloma Jeretic, and Samuel R. Bowman. 2019. [Investigating BERT’s knowledge of language: Five analysis methods with N…](https://md.research.elamur.ai/free/en/papers/warstadt-2019-investigating-bert-s-knowledge-language/)
39. Gail Weiss, Yoav Goldberg, and Eran Yahav. 2018. [On the practical computational power of finite precision RNNs for language recognition](https://md.research.elamur.ai/free/en/papers/weiss-2018-practical-computational-power-finite-precision/). In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers), pages 740–745, Melbourne, Australia. Associati…
40. Gail Weiss, Yoav Goldberg, and Eran Yahav. 2019. Learning deterministic weighted automata with queries and counterexamples. In H. Wallach, H. Larochelle, A. Beygelzimer, F. AlcheBuc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages 8560–8571. Curran Associ… [find](https://scholar.google.com/scholar?q=Gail+Weiss%2C+Yoav+Goldberg%2C+and+Eran+Yahav%2E+2019%2E+Learning+deterministic+weighted+automata+with+queries+and+counterexamples%2E+In+H%2E+Wallach%2C+H%2E+Larochelle%2C+A%2E+Beygelzimer%2C+F%2E+AlcheBuc%2C+E%2E+Fox%2C+and+R%2E+Ga)
41. Baosong Yang, Longyue Wang, Derek F. Wong, Lidia S. Chao, and Zhaopeng Tu. 2019. Assessing [find](https://scholar.google.com/scholar?q=Baosong+Yang%2C+Longyue+Wang%2C+Derek+F%2E+Wong%2C+Lidia+S%2E+Chao%2C+and+Zhaopeng+Tu%2E+2019%2E+Assessing)

*Updated 24 October 2026*