Relationships between the Computational Capabilities of Simple Recurrent Networks and Finite Automata (Special Section on Discrete Mathematics and Its Applications)

概要

論文の詳細を見る
In the filed of cognitive psychology, simple recurrent networks are used for modeling the natural language processing in the human brain. For example, Elman experimentally showed that the simple recurrent networks can predict the rightmost word in sentential forms of a particular grammar which can generate compound sentences with high probability. Concerning these results, it is natural to ask whether the computational capability of the simple recurrent networks is sufficient to recognize natural languages. In this paper, we assume that the range of a function computed at each gate of a simple recurrent network is a finite set. This is a quite realistic assumption, because we cannot physically implement a gate whose range is an infinite set. Then, we define equivalence relations between simple recurrent networks and Mealy machines or Moore machines, which are finite automata with output. Then, under our assumption, we show (1) a construction of a Mealy machine which simulates a given simple recurrent network, and (2) a construction of a simple recurrent network which simulates a given Moore machine. From these two constructions, we can conclude that the computational capability of the simple recurrent networks is equal to that of finite automata with output under our assumption.
社団法人電子情報通信学会の論文
2001-05-01