---
title: "How Can Self-Attention Networks Recognize Dyck-n Languages?"
description: "The paper asks whether self-attention (SA) networks, essentially Transformer encoders without… 26 references, cited by 28 papers here."
authors: ["Javid Ebrahimi", "Dhruv Gelda", "Wei Zhang"]
year: 2020
venue: "Findings of the Association for Computational Linguistics: EMNLP 2020"
source: "https://aclanthology.org/2020.findings-emnlp.384/"
doi: "10.18653/v1/2020.findings-emnlp.384"
arxiv: "2010.04303"
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/ebrahimi-2020-how-can-self-attention-networks/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/ebrahimi-2020-how-can-self-attention-networks/)

[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/6/) / How Can Self-Attention Networks Recognize Dyck-n Languages?

# How Can Self-Attention Networks Recognize Dyck-n Languages?

**Authors:** [Javid Ebrahimi](https://md.research.elamur.ai/free/en/authors/javid-ebrahimi/), Dhruv Gelda and [Wei Zhang](https://md.research.elamur.ai/free/en/authors/wei-zhang/) · **Year:** 2020 · **Venue:** [Findings of the Association for Computational Linguistics: EMNLP 2020](https://md.research.elamur.ai/free/en/venues/findings/) ([Findings of the Association for Computational Linguistics 2020](https://md.research.elamur.ai/free/en/venues/findings/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.findings-emnlp.384/) · [PDF](https://aclanthology.org/2020.findings-emnlp.384.pdf) · [DOI 10.18653/v1/2020.findings-emnlp.384](https://doi.org/10.18653/v1/2020.findings-emnlp.384) · [arXiv 2010.04303](https://arxiv.org/abs/2010.04303) · [OpenAlex](https://openalex.org/W3099140684)

**Citations:** 13 citations (OpenAlex, 2026-10-14) · [28](https://md.research.elamur.ai/free/en/papers/ebrahimi-2020-how-can-self-attention-networks/cited-by/) in our library, of the 149,439 papers whose bibliographies we read

## Summary
The paper asks whether self-attention (SA) networks, essentially Transformer encoders without recurrence, can learn the Dyck-n (D n) languages of balanced strings with n bracket types. Earlier theoretical and empirical work had suggested this is hard for them. The authors frame recognition as next-symbol transduction: at every position the model must predict the full set of valid next brackets. This is a multi-label task trained with binary cross-entropy. They compare SA with and without a prepended starting symbol T (SA+ and SA−) and unidirectional LSTM baselines, all of similar size. Training data come from a PCFG following Suzgun et al. (2019), and test sequences are longer than any seen in training. The starting symbol strongly improves SA's generalization to longer and deeper strings. Second-layer attention maps in SA+ behave like a stack: each closing bracket attends to the most recent unmatched opening bracket, or to T when the stack is empty. SA+ is roughly on par with LSTMs. The authors argue this shows hierarchy can be learned without recursion, by learning to look up the correct head token.

## Key points
- **Setup:**
  - SA models have 2 layers, 4 heads and d = 256; the LSTMs use 320-dimensional states.
  - All models have about 1.6M parameters and are trained with Adam and no dropout.
  - Data for D1–D4: 32k training strings of length 2–50, 3.2k validation strings of length 52–74, and 10k test strings split between lengths 76–100 and 102–126.
- **D2 at lengths 102–126:**
  - SA− essentially fails (0.006%).
  - SA+ reaches 58.82%.
  - LSTM− is better here at 73.20%, the only comparison SA+ loses to LSTM−.
- **Other D n results:**
  - SA+ scores about 93% on lengths 76–100 for D2–D4.
  - On the longest bin it improves with more bracket types (66.88% for D3, 72.38% for D4), whereas LSTM accuracy declines as n grows.
- **Starting symbol:** Adding T helps SA but slightly hurts LSTMs.
- **Stack compatibility:**
  - The authors define a compatibility metric that checks whether attention matches a stack-based recognizer.
  - SA+ is perfectly compatible on training-range lengths, while SA− on D2 is near zero.
  - For SA+, accuracy and compatibility correlate at about 90% or higher (Pearson) across lengths 50–100.

*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

- [Visa](https://md.research.elamur.ai/free/en/companies/visa/) — Company, Foster City, United States · 2 works · 106 citations

📚 Shelves (5): [🖥️ Computer Science](https://md.research.elamur.ai/free/en/shelves/computer-science/) · 16,667 works · [🤖 Artificial Intelligence](https://md.research.elamur.ai/free/en/shelves/computer-science/artificial-intelligence/) · 16,194 works · [🎭 Arts and Humanities](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/) · 16,039 works · [🗣️ Language and Linguistics](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/language-and-linguistics/) · 15,891 works · [🧮 Computational Theory and Mathematics](https://md.research.elamur.ai/free/en/shelves/computer-science/computational-theory-and-mathematics/) · 252 works

## Cite

Cite as: Javid Ebrahimi, Dhruv Gelda and Wei Zhang. 2020. How Can Self-Attention Networks Recognize Dyck-n Languages?. Findings of the Association for Computational Linguistics: EMNLP 2020.

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

```bibtex
@inproceedings{ebrahimi2020how,
  title = {{How Can Self-Attention Networks Recognize Dyck-n Languages?}},
  author = {Javid Ebrahimi, Dhruv Gelda and Wei Zhang},
  booktitle = {Findings of the Association for Computational Linguistics: EMNLP 2020},
  year = {2020},
  doi = {10.18653/v1/2020.findings-emnlp.384},
  eprint = {2010.04303},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.18653/v1/2020.findings-emnlp.384}
}
```

- [← previous Englishes in the Expanding Circle: Focus on Asia](https://md.research.elamur.ai/free/en/papers/kirkpatrick-2020-englishes-expanding-circle-focus-asia/)
- [next → QANom: Question-Answer driven SRL for Nominalizations](https://md.research.elamur.ai/free/en/papers/klein-2020-qanom-question-answer-driven-srl/)
- [↑ back to papers of 2020](https://md.research.elamur.ai/free/en/papers/2020/page/6/)

## References

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

1. Jean-Philippe Bernardy. 2018. Can recurrent neural networks learn nested recursion? LiLT (Linguistic Issues in Language Technology), 16(1). [find](https://scholar.google.com/scholar?q=Jean%2DPhilippe+Bernardy%2E+2018%2E+Can+recurrent+neural+networks+learn+nested+recursion%3F+LiLT+%28Linguistic+Issues+in+Language+Technology%29%2C+16%281%29%2E)
2. Samuel R Bowman, Gabor Angeli, Christopher Potts, and Christopher D Manning. 2015. [A large annotated corpus for learning natural language inference](https://md.research.elamur.ai/free/en/papers/bowman-2015-large-annotated-corpus-learning-natural/). In EMNLP.
3. Noam Chomsky and Marcel P Schützenberger. 1959. The algebraic theory of context-free languages. In Studies in Logic and the Foundations of Mathematics, volume 26, pages 118–161. Elsevier. [find](https://scholar.google.com/scholar?q=Noam+Chomsky+and+Marcel+P+Schu%CC%88tzenberger%2E+1959%2E+The+algebraic+theory+of+context%2Dfree+languages%2E+In+Studies+in+Logic+and+the+Foundations+of+Mathematics%2C+volume+26%2C+pages+118%E2%80%93161%2E+Elsevier%2E)
4. Sreerupa Das, C Lee Giles, and Guo-Zheng Sun. 1992. Learning context-free grammars: Capabilities and limitations of a recurrent neural network with an external stack memory. In Proceedings of The Fourteenth Annual Conference of Cognitive Science Society. Indiana University, page 14. [find](https://scholar.google.com/scholar?q=Sreerupa+Das%2C+C+Lee+Giles%2C+and+Guo%2DZheng+Sun%2E+1992%2E+Learning+context%2Dfree+grammars%3A+Capabilities+and+limitations+of+a+recurrent+neural+network+with+an+external+stack+memory%2E+In+Proceedings+of+The+Four)
5. Jeffrey L Elman. 1990. Finding structure in time. Cognitive science, 14(2):179–211. [find](https://scholar.google.com/scholar?q=Jeffrey+L+Elman%2E+1990%2E+Finding+structure+in+time%2E+Cognitive+science%2C+14%282%29%3A179%E2%80%93211%2E)
6. 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)
7. 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)
8. Yiding Hao, William Merrill, Dana Angluin, Robert Frank, Noah Amsel, Andrew Benz, and Simon Mendelsohn. 2018. Context-free transductions with neural stacks. In Proceedings of the 2018 EMNLP Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP. [find](https://scholar.google.com/scholar?q=Yiding+Hao%2C+William+Merrill%2C+Dana+Angluin%2C+Robert+Frank%2C+Noah+Amsel%2C+Andrew+Benz%2C+and+Simon+Mendelsohn%2E+2018%2E+Context%2Dfree+transductions+with+neural+stacks%2E+In+Proceedings+of+the+2018+EMNLP+Workshop+B)
9. 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)
10. Angelos Katharopoulos, Apoorv Vyas, Nikolaos Pappas, and François Fleuret. 2020. Transformers are rnns: Fast autoregressive transformers with linear attention. In ICML. [find](https://scholar.google.com/scholar?q=Angelos+Katharopoulos%2C+Apoorv+Vyas%2C+Nikolaos+Pappas%2C+and+Franc%CC%A7ois+Fleuret%2E+2020%2E+Transformers+are+rnns%3A+Fast+autoregressive+transformers+with+linear+attention%2E+In+ICML%2E)
11. Eugene Kharitonov and Rahma Chaabouni. 2020. What they do when in doubt: a study of inductive biases in seq2seq learners. arXiv preprint arXiv:2006.14953. — [arXiv:2006.14953](https://arxiv.org/abs/2006.14953) [find](https://scholar.google.com/scholar?q=Eugene+Kharitonov+and+Rahma+Chaabouni%2E+2020%2E+What+they+do+when+in+doubt%3A+a+study+of+inductive+biases+in+seq2seq+learners%2E+arXiv+preprint+arXiv%3A2006%2E14953%2E+%E2%80%94+%5BarXiv%3A2006%2E14953%5D%28https%3A%2F%2Farxiv%2Eorg%2Fabs%2F20)
12. Diederik P Kingma and Jimmy Ba. 2015. [Adam: A method for stochastic optimization](https://md.research.elamur.ai/free/en/papers/kingma-2014-adam-method-stochastic-optimization/). In ICLR.
13. William Merrill, Gail Weiss, Yoav Goldberg, Roy Schwartz, Noah A Smith, and Eran Yahav. 2020. A formal hierarchy of rnn architectures. In ACL. [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+In+ACL%2E)
14. 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)
15. Jorge Pérez, Javier Marinković, and Pablo Barceló. 2019. On the turing completeness of modern neural network architectures. In ICLR. [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+ICLR%2E)
16. 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. [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)
17. Yikang Shen, Shawn Tan, Arian Hosseini, Zhouhan Lin, Alessandro Sordoni, and Aaron C Courville. 2019. Ordered memory. In NeurIPS. [find](https://scholar.google.com/scholar?q=Yikang+Shen%2C+Shawn+Tan%2C+Arian+Hosseini%2C+Zhouhan+Lin%2C+Alessandro+Sordoni%2C+and+Aaron+C+Courville%2E+2019%2E+Ordered+memory%2E+In+NeurIPS%2E)
18. Hava T Siegelmann and Eduardo D Sontag. 1992. On the computational power of neural nets. In Proceedings of the fifth annual workshop on Computational learning theory, pages 440–449. [find](https://scholar.google.com/scholar?q=Hava+T+Siegelmann+and+Eduardo+D+Sontag%2E+1992%2E+On+the+computational+power+of+neural+nets%2E+In+Proceedings+of+the+fifth+annual+workshop+on+Computational+learning+theory%2C+pages+440%E2%80%93449%2E)
19. Natalia Skachkova, Thomas Alexander Trost, and Dietrich Klakow. 2018. [Closing brackets with recurrent neural networks](https://md.research.elamur.ai/free/en/papers/skachkova-2018-closing-brackets-recurrent-neural-networks/). In Proceedings of the 2018 EMNLP Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP, pages 232– 239.
20. Mark Steijvers and Peter Grünwald. 1996. A recurrent network that performs a context-sensitive prediction task. In Proceedings of the 18th annual conference of the cognitive science society, pages 335–339. [find](https://scholar.google.com/scholar?q=Mark+Steijvers+and+Peter+Gru%CC%88nwald%2E+1996%2E+A+recurrent+network+that+performs+a+context%2Dsensitive+prediction+task%2E+In+Proceedings+of+the+18th+annual+conference+of+the+cognitive+science+society%2C+pages+33)
21. Mirac Suzgun, Sebastian Gehrmann, Yonatan Belinkov, and Stuart M Shieber. 2019. Memory-augmented recurrent neural networks can learn generalized dyck languages. arXiv preprint arXiv:1911.03329. — [arXiv:1911.03329](https://arxiv.org/abs/1911.03329) [find](https://scholar.google.com/scholar?q=Mirac+Suzgun%2C+Sebastian+Gehrmann%2C+Yonatan+Belinkov%2C+and+Stuart+M+Shieber%2E+2019%2E+Memory%2Daugmented+recurrent+neural+networks+can+learn+generalized+dyck+languages%2E+arXiv+preprint+arXiv%3A1911%2E03329%2E+%E2%80%94+%5BarX)
22. Ke M Tran, Arianna Bisazza, and Christof Monz. 2018. The importance of being recurrent for modeling hierarchical structure. In EMNLP. [find](https://scholar.google.com/scholar?q=Ke+M+Tran%2C+Arianna+Bisazza%2C+and+Christof+Monz%2E+2018%2E+The+importance+of+being+recurrent+for+modeling+hierarchical+structure%2E+In+EMNLP%2E)
23. 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 NeurIPS.
24. 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 ACL.
25. Xiang Yu, Ngoc Thang Vu, and Jonas Kuhn. 2019. Learning the dyck language with attention-based seq2seq models. In Proceedings of the 2019 ACL Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP, pages 138–146. [find](https://scholar.google.com/scholar?q=Xiang+Yu%2C+Ngoc+Thang+Vu%2C+and+Jonas+Kuhn%2E+2019%2E+Learning+the+dyck+language+with+attention%2Dbased+seq2seq+models%2E+In+Proceedings+of+the+2019+ACL+Workshop+BlackboxNLP%3A+Analyzing+and+Interpreting+Neural+Ne)
26. Nikita Nangia and Samuel Bowman. 2018. Listops: A diagnostic dataset for latent tree learning. In Proceedings of the 2018 NAACL: Student Research Workshop. [find](https://scholar.google.com/scholar?q=Nikita+Nangia+and+Samuel+Bowman%2E+2018%2E+Listops%3A+A+diagnostic+dataset+for+latent+tree+learning%2E+In+Proceedings+of+the+2018+NAACL%3A+Student+Research+Workshop%2E)

*Updated 30 October 2026*