---
title: "LSTM Networks Can Perform Dynamic Counting — Suzgun 2019"
description: "Specifically, it tests whether they can emulate k-counter automata whose counters may change… 36 references, cited by 41 papers here."
authors: ["Mirac Suzgun", "Yonatan Belinkov", "Stuart Shieber", "Sebastian Gehrmann"]
year: 2019
venue: "Proceedings of the Workshop on Deep Learning and Formal Languages: Building Bridges"
source: "https://aclanthology.org/W19-3905/"
doi: "10.18653/v1/w19-3905"
arxiv: "1906.03648"
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/suzgun-2019-lstm-networks-can-perform-dynamic/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/suzgun-2019-lstm-networks-can-perform-dynamic/)

[home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [2019](https://md.research.elamur.ai/free/en/papers/2019/page/5/) / LSTM Networks Can Perform Dynamic Counting

# LSTM Networks Can Perform Dynamic Counting

**Authors:** [Mirac Suzgun](https://md.research.elamur.ai/free/en/authors/mirac-suzgun/), [Yonatan Belinkov](https://md.research.elamur.ai/free/en/authors/yonatan-belinkov/), [Stuart Shieber](https://md.research.elamur.ai/free/en/authors/stuart-m-shieber/) and [Sebastian Gehrmann](https://md.research.elamur.ai/free/en/authors/sebastian-gehrmann/) · **Year:** 2019 · **Venue:** Proceedings of the Workshop on Deep Learning and Formal Languages: Building Bridges · **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/W19-3905/) · [PDF](https://aclanthology.org/W19-3905.pdf) · [DOI 10.18653/v1/w19-3905](https://doi.org/10.18653/v1/w19-3905) · [arXiv 1906.03648](https://arxiv.org/abs/1906.03648) · [OpenAlex](https://openalex.org/W2948182330)

**Citations:** 48 citations (OpenAlex, 2026-10-14) · [41](https://md.research.elamur.ai/free/en/papers/suzgun-2019-lstm-networks-can-perform-dynamic/cited-by/) in our library, of the 149,439 papers whose bibliographies we read

## Summary
The paper asks whether recurrent networks with finite precision can do more than the simple one-turn counting that earlier work found in LSTMs trained on aⁿbⁿ and aⁿbⁿcⁿ. Specifically, it tests whether they can emulate k-counter automata whose counters may change direction any number of times, which the authors call dynamic counting. The authors compare small single-layer Elman-RNNs, GRUs and LSTMs on four synthetic tasks: Dyck-1, two shuffle languages built from disjoint Dyck-1 bracket pairs (Shuffle-2 and Shuffle-6), and Dyck-2. At each step, a model must predict the set of characters that may legally come next. A sequence counts as recognized only if every prediction is correct. LSTMs mastered Dyck-1 and the shuffle languages and generalized to sequences beyond the training range. Inspecting their cell states showed units behaving as explicit counters. No architecture learned Dyck-2, which requires a stack. The work therefore gives empirical support to the theory of Weiss et al. (2018) and maps out what gated RNNs can and cannot represent hierarchically.

## Key points
- **Training setup.** Inputs are one-hot and targets are k-hot. Training minimizes mean-squared error with sigmoid outputs thresholded at 0.5, using Adam (α = 0.001). Each experiment was repeated ten times with no embeddings or dropout.
- **Model sizes.** All networks are tiny. They use 3 hidden units for Dyck-1, 4 for Dyck-2, 4 for Shuffle-2 and 8 for Shuffle-6.
- **Minimal LSTMs.** A one-unit LSTM recognizes Dyck-1 by incrementing on "(" and decrementing on ")". A two-unit LSTM handles Shuffle-2.
- **Counters in Shuffle-6.** In a Shuffle-6 LSTM, six of the eight cell units track the nesting depth of each bracket type, which amounts to emulating a DCA₆. Some units also counted sequence length.
- **Dyck-2 failure.** Dyck-2 training data consisted of 10,000 sequences of length 2–50, sampled from a PCFG with p = 1/2 and q = 1/4. All models failed on this language. The last-closing-bracket task of Skachkova et al. (2018) was solved perfectly, but only through counting tricks rather than genuine recognition of the language.

*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

- [Harvard University](https://md.research.elamur.ai/free/en/universities/harvard-university/) — University, Cambridge, United States · 112 works · 42,023 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: Mirac Suzgun, Yonatan Belinkov, Stuart Shieber and Sebastian Gehrmann. 2019. LSTM Networks Can Perform Dynamic Counting. Proceedings of the Workshop on Deep Learning and Formal Languages: Building Bridges.

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

```bibtex
@inproceedings{suzgun2019lstm,
  title = {{LSTM Networks Can Perform Dynamic Counting}},
  author = {Mirac Suzgun, Yonatan Belinkov, Stuart Shieber and Sebastian Gehrmann},
  booktitle = {Proceedings of the Workshop on Deep Learning and Formal Languages: Building Bridges},
  year = {2019},
  doi = {10.18653/v1/w19-3905},
  eprint = {1906.03648},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.18653/v1/w19-3905}
}
```

- [← previous hULMonA: The Universal Language Model in Arabic](https://md.research.elamur.ai/free/en/papers/eljundi-2019-hulmona-universal-language-model-arabic/)
- [next → VerbAtlas: a Novel Large-Scale Verbal Semantic Resource and Its Application to Semantic Role Labeling](https://md.research.elamur.ai/free/en/papers/fabio-2019-verbatlas-novel-large-scale-verbal/)
- [↑ back to papers of 2019](https://md.research.elamur.ai/free/en/papers/2019/page/5/)

## References

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

1. networks learn nested recursion? LiLT (Linguistic Issues in Language Technology), 16(1). [find](https://scholar.google.com/scholar?q=networks+learn+nested+recursion%3F+LiLT+%28Linguistic+Issues+in+Language+Technology%29%2C+16%281%29%2E)
2. Anthony Bau, Yonatan Belinkov, Hassan Sajjad, Nadir Durrani, Fahim Dalvi, and James Glass. 2019. Identifying and controlling important neurons in neural machine translation. In International Conference on Learning Representations. [find](https://scholar.google.com/scholar?q=Anthony+Bau%2C+Yonatan+Belinkov%2C+Hassan+Sajjad%2C+Nadir+Durrani%2C+Fahim+Dalvi%2C+and+James+Glass%2E+2019%2E+Identifying+and+controlling+important+neurons+in+neural+machine+translation%2E+In+International+Conferenc)
3. Mikael Bodén and Janet Wiles. 2000. Context-free and context-sensitive dynamics in recurrent neural networks. Connection Science, 12(3-4):197–210. [find](https://scholar.google.com/scholar?q=Mikael+Bode%CC%81n+and+Janet+Wiles%2E+2000%2E+Context%2Dfree+and+context%2Dsensitive+dynamics+in+recurrent+neural+networks%2E+Connection+Science%2C+12%283%2D4%29%3A197%E2%80%93210%2E)
4. Mikael Bodén, Janet Wiles, Bradley Tonkes, and Alan Blair. 1999. Learning to predict a context-free lan-Jean-Philippe Bernardy. 2018. Can recurrent neural Sepp Hochreiter. 1998. The vanishing gradient problem during learning recurrent neural nets and problem solutions. International Journal of Unce… [find](https://scholar.google.com/scholar?q=Mikael+Bode%CC%81n%2C+Janet+Wiles%2C+Bradley+Tonkes%2C+and+Alan+Blair%2E+1999%2E+Learning+to+predict+a+context%2Dfree+lan%2DJean%2DPhilippe+Bernardy%2E+2018%2E+Can+recurrent+neural+Sepp+Hochreiter%2E+1998%2E+The+vanishing+gradien)
5. Kyunghyun Cho, Bart Van Merriënboer, Caglar Gulcehre, Dzmitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio. 2014. [Learning phrase representations using RNN encoder-decoder for statistical machine translation](https://md.research.elamur.ai/free/en/papers/cho-2014-learning-phrase-representations-rnn-encoder/). arXiv preprint arXiv:1406.1078.
6. 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)
7. Noam Chomsky and Marcel P Schützenberger. 1963. The algebraic theory of context-free languages. In Studies in Logic and the Foundations of Mathematics, volume 35, pages 118–161. Elsevier. [find](https://scholar.google.com/scholar?q=Noam+Chomsky+and+Marcel+P+Schu%CC%88tzenberger%2E+1963%2E+The+algebraic+theory+of+context%2Dfree+languages%2E+In+Studies+in+Logic+and+the+Foundations+of+Mathematics%2C+volume+35%2C+pages+118%E2%80%93161%2E+Elsevier%2E)
8. Armand Joulin and Tomas Mikolov. 2015. Inferring algorithmic patterns with stack-augmented recurrent nets. In Advances in neural information processing systems, pages 190–198. [find](https://scholar.google.com/scholar?q=Armand+Joulin+and+Tomas+Mikolov%2E+2015%2E+Inferring+algorithmic+patterns+with+stack%2Daugmented+recurrent+nets%2E+In+Advances+in+neural+information+processing+systems%2C+pages+190%E2%80%93198%2E)
9. Diederik P Kingma and Jimmy Ba. 2014. [Adam: A method for stochastic optimization](https://md.research.elamur.ai/free/en/papers/kingma-2014-adam-method-stochastic-optimization/). arXiv preprint arXiv:1412.6980.
10. Fahim Dalvi, Nadir Durrani, Hassan Sajjad, Yonatan Belinkov, D. Anthony Bau, and James Glass. 2019. What is one grain of sand in the desert? analyzing individual neurons in deep NLP models. In Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence. [find](https://scholar.google.com/scholar?q=Fahim+Dalvi%2C+Nadir+Durrani%2C+Hassan+Sajjad%2C+Yonatan+Belinkov%2C+D%2E+Anthony+Bau%2C+and+James+Glass%2E+2019%2E+What+is+one+grain+of+sand+in+the+desert%3F+analyzing+individual+neurons+in+deep+NLP+models%2E+In+Proceed)
11. Frédéric Magniez, Claire Mathieu, and Ashwin Nayak. 2014. Recognizing well-parenthesized expressions in the streaming model. SIAM Journal on Computing, 43(6):1880–1905. [find](https://scholar.google.com/scholar?q=Fre%CC%81de%CC%81ric+Magniez%2C+Claire+Mathieu%2C+and+Ashwin+Nayak%2E+2014%2E+Recognizing+well%2Dparenthesized+expressions+in+the+streaming+model%2E+SIAM+Journal+on+Computing%2C+43%286%29%3A1880%E2%80%931905%2E)
12. 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)
13. Tomáš Mikolov, Martin Karafiát, Lukáš Burget, Jan Černockỳ, and Sanjeev Khudanpur. 2010. Recurrent neural network based language model. In Eleventh annual conference of the international speech communication association. [find](https://scholar.google.com/scholar?q=Toma%CC%81s%CC%8C+Mikolov%2C+Martin+Karafia%CC%81t%2C+Luka%CC%81s%CC%8C+Burget%2C+Jan+C%CC%8Cernocky%CC%80%2C+and+Sanjeev+Khudanpur%2E+2010%2E+Recurrent+neural+network+based+language+model%2E+In+Eleventh+annual+conference+of+the+international+speech)
14. Tristan Deleu and Joseph Dureau. 2016. Learning operations on a stack with Neural Turing Machines. arXiv preprint arXiv:1612.00827. — [arXiv:1612.00827](https://arxiv.org/abs/1612.00827) [find](https://scholar.google.com/scholar?q=Tristan+Deleu+and+Joseph+Dureau%2E+2016%2E+Learning+operations+on+a+stack+with+Neural+Turing+Machines%2E+arXiv+preprint+arXiv%3A1612%2E00827%2E+%E2%80%94+%5BarXiv%3A1612%2E00827%5D%28https%3A%2F%2Farxiv%2Eorg%2Fabs%2F1612%2E00827%29)
15. Marvin Lee Minsky. 1967. Computation: Finite and Infinite Machines. Prentice-Hall Englewood Cliffs. [find](https://scholar.google.com/scholar?q=Marvin+Lee+Minsky%2E+1967%2E+Computation%3A+Finite+and+Infinite+Machines%2E+Prentice%2DHall+Englewood+Cliffs%2E)
16. 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)
17. Paul Rodriguez. 2001. Simple recurrent networks learn context-free and context-sensitive languages by counting. Neural computation, 13(9):2093– 2118. [find](https://scholar.google.com/scholar?q=Paul+Rodriguez%2E+2001%2E+Simple+recurrent+networks+learn+context%2Dfree+and+context%2Dsensitive+languages+by+counting%2E+Neural+computation%2C+13%289%29%3A2093%E2%80%93+2118%2E)
18. 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)
19. Paul Rodriguez and Janet Wiles. 1998. Recurrent neural networks can learn to implement symbol-sensitive counting. In Advances in Neural Information Processing Systems, pages 87–93. [find](https://scholar.google.com/scholar?q=Paul+Rodriguez+and+Janet+Wiles%2E+1998%2E+Recurrent+neural+networks+can+learn+to+implement+symbol%2Dsensitive+counting%2E+In+Advances+in+Neural+Information+Processing+Systems%2C+pages+87%E2%80%9393%2E)
20. 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)
21. 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. [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)
22. Seymour Ginsburg and Edwin H Spanier. 1966. Finite-turn pushdown automata. SIAM Journal on Control, 4(3):429–453. [find](https://scholar.google.com/scholar?q=Seymour+Ginsburg+and+Edwin+H+Spanier%2E+1966%2E+Finite%2Dturn+pushdown+automata%2E+SIAM+Journal+on+Control%2C+4%283%29%3A429%E2%80%93453%2E)
23. Xing Shi, Kevin Knight, and Deniz Yuret. 2016. Why neural translations are the right length. In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, pages 2278–2282. [find](https://scholar.google.com/scholar?q=Xing+Shi%2C+Kevin+Knight%2C+and+Deniz+Yuret%2E+2016%2E+Why+neural+translations+are+the+right+length%2E+In+Proceedings+of+the+2016+Conference+on+Empirical+Methods+in+Natural+Language+Processing%2C+pages+2278%E2%80%932282%2E)
24. Alex Graves, Greg Wayne, and Ivo Danihelka. 2014. Neural Turing Machines. arXiv preprint arXiv:1410.5401. [find](https://scholar.google.com/scholar?q=Alex+Graves%2C+Greg+Wayne%2C+and+Ivo+Danihelka%2E+2014%2E+Neural+Turing+Machines%2E+arXiv+preprint+arXiv%3A1410%2E5401%2E)
25. Hava T Siegelmann and Eduardo D Sontag. 1995. On the computational power of neural nets. Journal of computer and system sciences, 50(1):132–150. [find](https://scholar.google.com/scholar?q=Hava+T+Siegelmann+and+Eduardo+D+Sontag%2E+1995%2E+On+the+computational+power+of+neural+nets%2E+Journal+of+computer+and+system+sciences%2C+50%281%29%3A132%E2%80%93150%2E)
26. Edward Grefenstette, Karl Moritz Hermann, Mustafa Suleyman, and Phil Blunsom. 2015. Learning to transduce with unbounded memory. In Advances in Neural Information Processing Systems, pages 1828–1836. [find](https://scholar.google.com/scholar?q=Edward+Grefenstette%2C+Karl+Moritz+Hermann%2C+Mustafa+Suleyman%2C+and+Phil+Blunsom%2E+2015%2E+Learning+to+transduce+with+unbounded+memory%2E+In+Advances+in+Neural+Information+Processing+Systems%2C+pages+1828%E2%80%931836%2E)
27. Natalia Skachkova, Thomas 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.
28. Yiding Hao, William Merrill, Dana Angluin, Robert Frank, Noah Amsel, Andrew Benz, and Simon Mendelsohn. 2018. Context-free transductions with neural stacks. arXiv preprint arXiv:1809.02836. [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+arXiv+preprint+arXiv%3A1809%2E02836%2E)
29. Mark Steijvers. 1996. A recurrent network that performs a context-sensitive prediction task. [find](https://scholar.google.com/scholar?q=Mark+Steijvers%2E+1996%2E+A+recurrent+network+that+performs+a+context%2Dsensitive+prediction+task%2E)
30. Mirac Suzgun, Yonatan Belinkov, and Stuart M Shieber. 2019. On evaluating the generalization of LSTM models in formal languages. Proceedings of the Society for Computation in Linguistics (SCiL), pages 277–286. [find](https://scholar.google.com/scholar?q=Mirac+Suzgun%2C+Yonatan+Belinkov%2C+and+Stuart+M+Shieber%2E+2019%2E+On+evaluating+the+generalization+of+LSTM+models+in+formal+languages%2E+Proceedings+of+the+Society+for+Computation+in+Linguistics+%28SCiL%29%2C+pages)
31. Bradley Tonkes and Janet Wiles. 1997. Learning a context-free task with a recurrent neural network: An analysis of stability. In In Proceedings of the Fourth Biennial Conference of the Australasian Cognitive Science Society. Citeseer. [find](https://scholar.google.com/scholar?q=Bradley+Tonkes+and+Janet+Wiles%2E+1997%2E+Learning+a+context%2Dfree+task+with+a+recurrent+neural+network%3A+An+analysis+of+stability%2E+In+In+Proceedings+of+the+Fourth+Biennial+Conference+of+the+Australasian+Co)
32. Leslie Valiant. 1973. Decision Procedures for Families of Deterministic Pushdown Automata. Ph.D. thesis, University of Warwick. [find](https://scholar.google.com/scholar?q=Leslie+Valiant%2E+1973%2E+Decision+Procedures+for+Families+of+Deterministic+Pushdown+Automata%2E+Ph%2ED%2E+thesis%2C+University+of+Warwick%2E)
33. Leslie G Valiant. 1974. The equivalence problem for deterministic finite-turn pushdown automata. Information and Control, 25(2):123–133. [find](https://scholar.google.com/scholar?q=Leslie+G+Valiant%2E+1974%2E+The+equivalence+problem+for+deterministic+finite%2Dturn+pushdown+automata%2E+Information+and+Control%2C+25%282%29%3A123%E2%80%93133%2E)
34. Leslie G Valiant. 1975. Regularity and related problems for deterministic pushdown automata. Journal of the ACM (JACM), 22(1):1–10. [find](https://scholar.google.com/scholar?q=Leslie+G+Valiant%2E+1975%2E+Regularity+and+related+problems+for+deterministic+pushdown+automata%2E+Journal+of+the+ACM+%28JACM%29%2C+22%281%29%3A1%E2%80%9310%2E)
35. Leslie G Valiant and Michael S Paterson. 1975. Deterministic one-counter automata. Journal of Computer and System Sciences, 10(3):340–350. [find](https://scholar.google.com/scholar?q=Leslie+G+Valiant+and+Michael+S+Paterson%2E+1975%2E+Deterministic+one%2Dcounter+automata%2E+Journal+of+Computer+and+System+Sciences%2C+10%283%29%3A340%E2%80%93350%2E)
36. 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.

*Updated 30 October 2026*