The Surprising Computational Power of Nondeterministic Stack RNNs. (arXiv:2210.01343v2 [cs.CL] UPDATED)

Traditional recurrent neural networks (RNNs) have a fixed, finite number of
memory cells. In theory (assuming bounded range and precision), this limits
their formal language recognition power to regular languages, and in practice,
RNNs have been shown to be unable to learn many context-free languages (CFLs).
In order to expand the class of languages RNNs recognize, prior work has
augmented RNNs with a nondeterministic stack data structure, putting them on
par with pushdown automata and increasing their language recognition power …

arxiv computational nondeterministic power stack