On the Linguistic Capacity of Real-Time Counter Automata
Open accessAbstract
Counter machines have achieved a newfound relevance to the field of natural language processing (NLP): recent work suggests some strong-performing recurrent neural networks utilize their memory as counters. Thus, one potential way to understand the success of these networks is to revisit the theory of counter computation. Therefore, we study the abilities of real-time counter machines as formal grammars, focusing on formal properties that are relevant for NLP models. We first show that several variants of the counter machine converge to express the same class of formal languages. We also prove that counter languages are closed under complement, union, intersection, and many other common set operations. Next, we show that counter machines cannot evaluate boolean expressions, even though they can weakly validate their syntax. This has implications for the interpretability and evaluation of neural network systems: successfully matching syntactic patterns does not guarantee that counter memory accurately encodes compositional semantics. Finally, we consider whether counter languages are semilinear. This work makes general contributions to the theory of formal languages that are of potential interest for understanding recurrent neural networks.
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?
The left side of Equation (1) implies that transformer decoders with Θ(n) steps can simulate real-time models of computation like automata or counter machines.
“The left side of Equation ( 1) implies that transformer decoders with Θ(n) steps can simulate real-time models of computation like automata or counter machines (Merrill, 2020).”
From The expressive power of transformers with chain of thought (2023) · cites this paper as Merrill, 2020
The Definitions (p. 2) and General Counter Machines (p. 3) describe real-time counter automata, but they do not address transformer decoders or whether Θ(n) decoder steps can simulate those machines. Searches for transformer-decoder simulation returned only passages about counter machines and recurrent networks. (LLM, conf=0.77)
Experimental — accuracy not yet measured
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
Hochreiter, S., & Schmidhuber, J. (1997) · Neural Computation · doi:10.1162/neco.1997.9.8.1735 · Cited by 102,318 · see citing works
Three models for the description of language
Chomsky, N. (1956) · IRE Transactions on Information Theory · doi:10.1109/tit.1956.1056813 · Cited by 2,846 · see citing works
Assessing the Ability of LSTMs to Learn Syntax-Sensitive Dependencies
Linzen, T., Emmanuel Dupoux, A., & Goldberg, Y. (2016) · Transactions of the Association for Computational Linguistics · doi:10.1162/tacl_a_00115 · Cited by 733 · 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
Natural Languages and Context-Free Languages
Pullum, G. K., & Gazdar, G. J. M. (1987) · Studies in linguistics and philosophy · doi:10.1007/978-94-009-3401-6_7 · Cited by 209 · 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
Natural languages and context-free languages
Pullum, G. K., & Gazdar, G. J. M. (1982) · Linguistics and Philosophy · doi:10.1007/bf00360802 · Cited by 195 · see citing works
The Convergence of Mildly Context-Sensitive Grammar Formalisms
Joshi, A. K., Vijay‐Shanker, K., & Weir, D. J. (1990) · ScholarlyCommons (University of Pennsylvania) · Cited by 192 · see citing works
Cross-Serial Dependencies in Dutch
Bresnan, J. W., Kaplan, R. M., Peters, S., & Zaenen, A. (1982) · Studies in linguistics and philosophy · doi:10.1007/978-94-009-3401-6_11 · Cited by 190 · see citing works
Turing machines with restricted memory access
Fischer, P. C. (1966) · Information and Control · doi:10.1016/s0019-9958(66)80003-7 · Cited by 99 · see citing works
MasakhaNER: Named entity recognition for African languages
(2021) · HAL · doi:10.1162/tacl · Cited by 61 · 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
Self-citationLSTM 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
Memory-Augmented Recurrent Neural Networks Can Learn Generalized Dyck LanguagesPreprint
Süzgün, M., Gehrmann, S., Belinkov, Y., & Shieber, S. M. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1911.03329 · Cited by 28 · see citing works
Flagged first, then by citations
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
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
Self-citationSequential 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
Self-citationOn the Ability and Limitations of Transformers to Recognize Formal Languages
Bhattamishra, S., Ahuja, K., & Goyal, N. (2020) · Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP) · doi:10.18653/v1/2020.emnlp-main.576 · Cited by 48 · see citing works
RNNs can generate bounded hierarchical languages with optimal memory
Hewitt, J., Hahn, M., Ganguli, S., Liang, P., & Manning, C. D. (2020) · Conference on Empirical Methods in Natural Language Processing (EMNLP) · doi:10.18653/v1/2020.emnlp-main.156 · Cited by 30 · 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
Self-citationThe Parallelism Tradeoff: Limitations of Log-Precision Transformers
Merrill, W., & Sabharwal, A. (2023) · Transactions of the Association for Computational Linguistics · doi:10.1162/tacl_a_00562 · Cited by 22 · see citing works
Self-citationThe EOS Decision and Length Extrapolation
Newman, B., Hewitt, J., Liang, P., & Manning, C. D. (2020) · BlackboxNLP Workshop on Analyzing and Interpreting Neural Networks for NLP (BlackboxNLP) · doi:10.18653/v1/2020.blackboxnlp-1.26 · Cited by 24 · 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
Self-citationFormal Language Theory Meets Modern NLPPreprint
Merrill, W. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2102.10094 · Cited by 8 · see citing works
Self-citationIrie, 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
The expressive power of transformers with chain of thought
Merrill, W., & Sabharwal, A. (2023) · arXiv · doi:10.48550/arxiv.2310.07923 · Cited by 4 · see citing works
Self-citationEl-Naggar, N., Madhyastha, P., & Weyde, T. (2023) · Conference of the European Chapter of the Association for Computational Linguistics: Student Research Workshop (EACL SRW) · doi:10.18653/v1/2023.eacl-srw.15 · Cited by 1 · see citing works
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
- Authors
- Merrill, W.
- Affiliations
- Allen Institute for Artificial Intelligence (US)
- Corresponding author
- Merrill, William
- Venue
- arXiv
- Publisher
- arXiv
- Published
- 2020
- ISSN
- 2331-8422 (ISSN-L)
- arXiv
- 2004.06866
- OpenAlex
- W2997645120
- Cited by
- 12
- References
- 12
- Citations by year
- 2026: 1 · 2024: 1 · 2023: 3 · 2021: 2 · 2020: 4 · 2019: 1
- Type
- posted content
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- Topics
- Physical Sciences › Computer Science › Computational Theory and Mathematics › semigroups and automata theory
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Computability, Logic, AI Algorithms
- Social Sciences › Arts and Humanities › Language and Linguistics › Syntax, Semantics, Linguistic Variation
- Keywords
- counter machines, formal languages, closure properties, Boolean formulas, neural network interpretability, recurrent neural networks, formal grammars, compositional semantics
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
