.png){kind=icon}
返回
.png){kind=icon}
.png){kind=icon}
摘要
En 中文
In order to refine the analysis of the computational power of discrete-time recurrent neural networks (NNs) between the binary-state NNs which are equivalent to finite automata (level 3 in the Chomsky hierarchy), and the analog-state NNs with rational weights which are Turing-complete (Chomsky level 0), we study an intermediate model alpha ANN of a binary-state NN that is extended with alpha > 0 extra analog-state neurons. For rational weights, we establish an analog neuron hierarchy 0ANNs subset of 1ANNs subset of 2ANNs subset of 3ANNs and separate its first two levels. In particular, 0ANNs coincide with the binary-state NNs (Chomsky level 3) being a proper subset of 1ANNs which accept at most context-sensitive languages (Chomsky level 1) including some non-context-free ones (above Chomsky level 2). We prove that the deterministic (context-free) language L-h= {0(n)1(n) vertical bar n > 1} cannot be recognized by any 1ANN even with real weights. In contrast, we show that deterministic pushdown automata accepting deterministic languages can be simulated by 2ANNs with rational weights, which thus constitute a proper superset of 1ANNs. Finally, we prove that the analog neuron hierarchy collapses to 3ANNs by showing that any Turing machine can be simulated by a 3ANN having rational weights, with linear-time overhead. (C) 2020 Elsevier Ltd. All rights reserved.
Keyword:
Recurrent neural network
Analog neuron hierarchy
Deterministic context-free language
Turing machine
Chomsky hierarchy
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
6.3
论文数:
8.3K
被引数:
3.0W
机构
引用论文
.png){kind=icon}
分享.png){kind=icon}
收藏
Bounds on the complexity of recurrent neural network implementations of finite state machines有限状态机的递归神经网络实现的复杂性的界限.png)
NEURAL NETWORKS.png)
NEURAL NETWORKSIF6.3
PREAI
分享收藏分享收藏
查看更多内容