Learning Context-Free Languages with Nondeterministic Stack RNNs
Not on the map. Why?
Abstract (arXiv)
We present a differentiable stack data structure that simultaneously and tractably encodes an exponential number of stack configurations, based on Lang's algorithm for simulating nondeterministic pushdown automata. We call the combination of this data structure with a recurrent neural network (RNN) controller a Nondeterministic Stack RNN. We compare our model against existing stack RNNs on various formal languages, demonstrating that our model converges more reliably to algorithmic behavior on deterministic tasks, and achieves lower cross-entropy on inherently nondeterministic tasks.
Key facts. Cited by 15 papers in the map (data through 14 Oct 2026). First posted on arXiv 9 Oct 2020.
Builds on
No reference list yet.
Built on by
Citing papers per year: 2021: 2; 2022: 3; 2023: 5; 2024: 3; 2025: 1; 2026: 1.
15 papers.
Sort:
By area:
- 2022Neural Networks and the Chomsky Hierarchycited by 217
- 2024Training Neural Networks as Recognizers of Formal Languagescited by 24
- 2023Practical Computational Power of Linear Transformers and Their Recurrent and Self-Referential Extensionscited by 20
- 2023Stack Attention: Improving the Ability of Transformers to Model Hierarchical Patternscited by 17
- 2021Learning Hierarchical Structures with Differentiable Nondeterministic Stackscited by 16
- 2021Formal Language Theory Meets Modern NLPcited by 9
- 2022The Surprising Computational Power of Nondeterministic Stack RNNscited by 6
- 2023Beam Tree Recursive Cellscited by 6
- 2023Recursion in Recursion: Two-Level Nested Recursion for Length Generalization with Scalabilitycited by 5
- 2023Efficient Beam Tree Recursioncited by 4
- 2024A Transformer with Stack Attentioncited by 2
- 2022Algorithms for Weighted Pushdown Automatacited by 1
3 more
- 2025Bearing Syntactic Fruit with Stack-Augmented Neural Networkscited by 1
- 2024Exploring Learnability in Memory-Augmented Recurrent Neural Networks: Precision, Stability, and Empirical Insightscited by 0
- 2026Transcript-Managed Transformers: Monotone Multi-Agent Collapse and Universality with Two Pop-Enabled Transcriptscited by 0
- 2026Transcript-Managed Transformers: Monotone Multi-Agent Collapse and Universality with Two Pop-Enabled Transcripts31 Jul 2026
- 2025Bearing Syntactic Fruit with Stack-Augmented Neural Networks5 Nov 2025
- 2024Training Neural Networks as Recognizers of Formal Languages11 Nov 2024
- 2024Exploring Learnability in Memory-Augmented Recurrent Neural Networks: Precision, Stability, and Empirical Insights4 Oct 2024
- 2024A Transformer with Stack Attention7 May 2024
- 2023Recursion in Recursion: Two-Level Nested Recursion for Length Generalization with Scalability8 Nov 2023
- 2023Practical Computational Power of Linear Transformers and Their Recurrent and Self-Referential Extensions24 Oct 2023
- 2023Stack Attention: Improving the Ability of Transformers to Model Hierarchical Patterns3 Oct 2023
- 2023Efficient Beam Tree Recursion20 Jul 2023
- 2023Beam Tree Recursive Cells31 May 2023
- 2022Algorithms for Weighted Pushdown Automata13 Oct 2022
- 2022The Surprising Computational Power of Nondeterministic Stack RNNs4 Oct 2022
3 more
- 2022Neural Networks and the Chomsky Hierarchy5 Jul 2022
- 2021Learning Hierarchical Structures with Differentiable Nondeterministic Stacks5 Sep 2021
- 2021Formal Language Theory Meets Modern NLP19 Feb 2021
- 2024Training Neural Networks as Recognizers of Formal Languagescited by 24
- 2024Training Neural Networks as Recognizers of Formal Languages11 Nov 2024
- 2022Neural Networks and the Chomsky Hierarchycited by 217
- 2023Practical Computational Power of Linear Transformers and Their Recurrent and Self-Referential Extensionscited by 20
- 2023Stack Attention: Improving the Ability of Transformers to Model Hierarchical Patternscited by 17
- 2021Learning Hierarchical Structures with Differentiable Nondeterministic Stackscited by 16
- 2021Formal Language Theory Meets Modern NLPcited by 9
- 2022The Surprising Computational Power of Nondeterministic Stack RNNscited by 6
- 2023Beam Tree Recursive Cellscited by 6
- 2023Recursion in Recursion: Two-Level Nested Recursion for Length Generalization with Scalabilitycited by 5
- 2023Efficient Beam Tree Recursioncited by 4
- 2024A Transformer with Stack Attentioncited by 2
- 2022Algorithms for Weighted Pushdown Automatacited by 1
- 2025Bearing Syntactic Fruit with Stack-Augmented Neural Networkscited by 1
12 most cited of 14 All 14 (JSON)
- 2026Transcript-Managed Transformers: Monotone Multi-Agent Collapse and Universality with Two Pop-Enabled Transcripts31 Jul 2026
- 2025Bearing Syntactic Fruit with Stack-Augmented Neural Networks5 Nov 2025
- 2024Exploring Learnability in Memory-Augmented Recurrent Neural Networks: Precision, Stability, and Empirical Insights4 Oct 2024
- 2024A Transformer with Stack Attention7 May 2024
- 2023Recursion in Recursion: Two-Level Nested Recursion for Length Generalization with Scalability8 Nov 2023
- 2023Practical Computational Power of Linear Transformers and Their Recurrent and Self-Referential Extensions24 Oct 2023
- 2023Stack Attention: Improving the Ability of Transformers to Model Hierarchical Patterns3 Oct 2023
- 2023Efficient Beam Tree Recursion20 Jul 2023
- 2023Beam Tree Recursive Cells31 May 2023
- 2022Algorithms for Weighted Pushdown Automata13 Oct 2022
- 2022The Surprising Computational Power of Nondeterministic Stack RNNs4 Oct 2022
- 2022Neural Networks and the Chomsky Hierarchy5 Jul 2022
12 newest of 14 All 14 (JSON)