On the Computational Power of RNNs

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.

Cited by in corpus (8)

• Theoretical Limitations of Self-Attention in Neural Sequence Models
• Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers
• Distance and Equivalence between Finite State Machines and Recurrent Neural Networks: Computational results
• Synthesizing Context-free Grammars from Recurrent Neural Networks (Extended Version)
• Self-Attention Networks Can Process Bounded Hierarchical Languages
• Learning and Generalization in RNNs
• Evaluating Attribution Methods using White-Box LSTMs
• Recognizing Long Grammatical Sequences Using Recurrent Networks Augmented With An External Differentiable Stack