The search functionality is under construction.
The search functionality is under construction.

Relationships between the Computational Capabilities of Simple Recurrent Networks and Finite Automata

Junnosuke MORIYA, Tetsuro NISHINO

  • Full Text Views

    0

  • Cite this

Summary :

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 right-most 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.

Publication
IEICE TRANSACTIONS on Fundamentals Vol.E84-A No.5 pp.1184-1194
Publication Date
2001/05/01
Publicized
Online ISSN
DOI
Type of Manuscript
Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category

Authors

Keyword