%0 Conference Paper %1 chen-etal-2018-recurrent %A Chen, Yining %A Gilroy, Sorcha %A Maletti, Andreas %A May, Jonathan %A Knight, Kevin %B Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers) %C New Orleans, Louisiana %D 2018 %I Association for Computational Linguistics %K formallanguages neuralnet readinggroup rnn %P 2261--2271 %R 10.18653/v1/N18-1205 %T Recurrent Neural Networks as Weighted Language Recognizers %U https://www.aclweb.org/anthology/N18-1205 %X 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. In summary, this shows that approximations and heuristic algorithms are necessary in practical applications of those RNNs.

@inproceedings{chen-etal-2018-recurrent, 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. In summary, this shows that approximations and heuristic algorithms are necessary in practical applications of those RNNs.}, added-at = {2020-07-15T14:52:21.000+0200}, address = {New Orleans, Louisiana}, author = {Chen, Yining and Gilroy, Sorcha and Maletti, Andreas and May, Jonathan and Knight, Kevin}, biburl = {https://www.bibsonomy.org/bibtex/2d44c58ef4878e367065cad6b10c5ee54/albinzehe}, booktitle = {Proceedings of the 2018 Conference of the North {A}merican Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers)}, doi = {10.18653/v1/N18-1205}, interhash = {4f407442ee043ca3a59c0fcd8a49c2cb}, intrahash = {d44c58ef4878e367065cad6b10c5ee54}, keywords = {formallanguages neuralnet readinggroup rnn}, month = jun, pages = {2261--2271}, publisher = {Association for Computational Linguistics}, timestamp = {2020-07-15T14:52:21.000+0200}, title = {Recurrent Neural Networks as Weighted Language Recognizers}, url = {https://www.aclweb.org/anthology/N18-1205}, year = 2018 }