Title: Recurrent Neural Networks as Weighted Language Recognizers,
Abstract: We investigate the computational complexity of various problems for simple
recurrent neural networks (RNNs) as formal models for recognizing weighted
languages. We focus on the single-layer, ReLU-activation, rational-weight RNNs
with softmax, which are commonly used in natural language processing
applications. We show that most problems for such RNNs are undecidable,
including consistency, equivalence, minimization, and the determination of the
highest-weighted string. However, for consistent RNNs the last problem becomes
decidable, although the solution length can surpass all computable bounds. If
additionally the string is limited to polynomial length, the problem becomes
NP-complete and APX-hard. In summary, this shows that approximations and
heuristic algorithms are necessary in practical applications of those RNNs.