本文研究了作为识别加权语言的形式模型的简单循环神经网络（RNN）的各种问题的计算复杂性，其中我们专注于单层、ReLU-激活、有理权重的 RNN，其使用广泛应用于自然语言处理应用程序。本文表明，这种 RNN 的大多数问题都是不可判定的，包括一致性、等价性、最小化和确定最高加权字符串。但对于一致性 RNN，最后一个问题变成可判定的，但其解决方案的长度可能超过所有可计算的界限。如果该字符串长度也被限制在多项式长度，那么该问题就变成了 NP-完全的并且是 APX-难的，因此本文表明了在这些 RNN 的实际应用程序中，逼近算法是必要的。

Nov, 2017

本研究旨在探讨不同复杂度的Tomita文法上，从常用的循环神经网络中提取确定有限状态自动机的性能表现。研究结果表明，随着底层文法复杂度的提高，大多数循环神经网络的提取性能逐渐降低。

Jan, 2018

本文研究了有限精度的RNNs，证明LSTM和Elman-RNN with ReLU activation比RNN with a squashing activation和GRU更加强大，可以实现计数行为，并且实验证明了LSTM学习了有效地使用计数机制。

May, 2018

通过使用一种被称为状态规范化的机制来处理以前递归神经网络（RNNs）的不足，从而提高RNNs的状态转移动态分析和解释性，并将其应用于自动机抽取，自然语言处理和计算机视觉中。

Jan, 2019

通过训练循环神经网络（RNN）来学习识别正则形式语言时使用的内部表示，我们研究了一个简单的解码函数，其将该 RNN 的状态映射到该语言的最小确定性有限自动机（MDFA）的状态，进而探讨了RNN内部表示与有限状态自动机之间的强结构关系，解释了RNN识别正式语法结构的能力。

Feb, 2019

本研究开发了一种表达式能力的RNN体系结构的形式化层次结构，这个层次结构基于空间复杂性和有理复发的形式属性。该研究将几种RNN变体放置在该层次结构中，并证明了LSTM不是合理的。我们还展示了通过堆叠多个图层或将它们与不同的池函数组合来扩展这些模型的表现力。我们的结果建立在“饱和”的RNN的理论基础之上。我们假设未饱和的RNN的实际可学习能力符合类似的层次结构，并通过对形式语言训练未饱和的网络的实验结果支持此假设。

Apr, 2020

通过给循环神经网络增加非确定性堆栈数据结构，可以扩展循环神经网络的语言识别能力，识别上下文无关语言和更多的非上下文无关语言，同时提高信息容量，这可以通过模拟向量堆栈来实现。

Oct, 2022

本文研究了RNN语言模型对概率分布的表示能力，发现简单的RNN等效于概率有限状态自动机，能够表示有限状态模型可表达的概率分布的严格子集，同时研究了用RNN表示确定性有限状态语言模型的空间复杂度。这些结果对于了解RNN语言模型的能力和限制具有重要意义。

Oct, 2023

通过研究基于递归神经网络的语言模型（LMs）的计算表达能力，本文通过扩展图灵完备性结果到概率情况，展示了有理加权RLM在无界计算时间下可以模拟任何概率图灵机。相反，在实时计算限制下，这些模型可以模拟确定性的实时有理PTM。

Oct, 2023

通过将递归神经网络语言模型连接到概率有限状态自动机，我们重新审视了递归神经网络语言模型的表征能力，并证明具有线性边界精度的递归神经网络语言模型可以表示任意的正则语言模型。

May, 2024