REVIEW 3 cited by
On the Computational Power of RNNs
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
read the original abstract
Recent neural network architectures such as the basic recurrent neural network (RNN) and Gated Recurrent Unit (GRU) have gained prominence as end-to-end learning architectures for natural language processing tasks. But what is the computational power of such systems? We prove that finite precision RNNs with one hidden layer and ReLU activation and finite precision GRUs are exactly as computationally powerful as deterministic finite automata. Allowing arbitrary precision, we prove that RNNs with one hidden layer and ReLU activation are at least as computationally powerful as pushdown automata. If we also allow infinite precision, infinite edge weights, and nonlinear output activation functions, we prove that GRUs are at least as computationally powerful as pushdown automata. All results are shown constructively.
Forward citations
Cited by 3 Pith papers
-
A Compositional Theory of Causally Masked Transformers
NoPE finite-precision causal transformers realize definite, R-trivial, locally R-trivial, or star-free languages according to whether attention is width-one window, sharp soft, cascaded, or ordinary floating-point soft.
-
An Algebraic View of the Expressivity of Recurrent Language Models
A unified algebraic account reduces RNN expressivity to syntactic monoid division in wreath products and shows diagonal state-space models realize every even-modulus counter under unsigned-integer quantization but non...
-
Universal Approximation Theorems for Dynamical Systems with Infinite-Time Horizon Guarantees
Neural ODEs can approximate Morse-Smale and continuous-attractor dynamical systems over infinite time in an ε-δ sense, provided limit-cycle periods are matched exactly.
Discussion (0). Continue with ORCID to comment.