Equivalence of Real-Time DPDA's and Discrete Extended Simple Recurrent Networks with Some Restrictions

概要

論文の詳細を見る
Elman introduced simple recurrent networks as computational models of human natural language processing. A simple recurrent network is a recurrent neural network whose gates are connected under certain restrictions. It is known that if the range of the function computed by each gate is a finite set (this type of simple recurrent networks is called a discrete simple recurrent network), the computational capability of discrete simple recurrent networks is equal to that of finite automata with output. In this paper, we introduce an extension of discrete simple recurrent networks whose computational powers are equivalent to those of real-time deterministic pushdown automata. Namely, we extend a discrete simple recurrent network in the following fashion: (1) its number of gates is linear in the input length, and (2) by using these gates it can provide stack manipulation where the stack depth is at most the input length.
社団法人電子情報通信学会の論文
2002-02-01