数理解析研究所講究録1093 巻 1999 年 188-193

188

単純口帰ネットワークの計算能力について
守谷純之介 (Junnosuke Moriya)

西野哲朗 (Tetsuro Nishino)

電気通信大学大学院電気通信学研究科〒 182-8585 東京都調布市調布ケ丘 1-5-1-mail: jmoriya@sw.cas.uec.ac.jp, nishino@sw.cas.uec.ac.jp$\mathrm{e}$1Introduction

In the filed of cognitive psychology, simple
recurrent networks are used for recognizing sequences of symbols and modeling the language
processing in the human brain. A simple recurrent network is a circuit which consists of a finite
number of gates, each of which computes a linear
function whose range is a closed interval 0.0, 1.
$[4, 5]$ . McClelland et al. showed on an experimental basis that simple recurrent networks cansimulate finite automata [8]. Rrthermore, Elman
showed on an experimental basis that simple recurrent networks can predict the rightmost wordin sentential forms of a particular context-freegrammar with high probability, after a learning
process based on the sample words which are generated by the grammar $[4, 5]$ . Concerning theseresults, it is natural ask whether the computational capability of simple recurrent networks issufficient to recognize natural languages or not.
It is known that processor nets used by Siegelmann and Sontag in [10] can simulate Turing Machines [10]. Processor nets are recurrent networks
which consist of a finite number of processors (orgates), each of which computes a saturated-linear
function. Siegelmann and Sontag showed the following facts in [10]: if the weights of the connections in a processor net are rational numbers, it
can simulate an arbitrary Turing Machine. The
proof of this proposition is constructive. Moreover, if the weights of the connections are real
numbers, processor nets can recognize arbitrary
languages and if the weights of connections areintegers, processor nets can only recognize regular languages. Note that when the weights arerational numbers (or real numbers), the numberof the sates of processor nets is infinite.
It is trivial that if each gate of simple recurrent
networks computes a saturated linear function,$[$$\mathrm{o}]$simple recurrent networks can simulate processor nets in a straightforward fashion. This meansthat simple recurrent networks can recognize recursive languages. In these works, however, therange of a function computed at each gate is infinite. In this paper, we assume that the range
of a function computed at each gate of a simple
recurrent networks is a finite set. This is a quite
realistic assumption especially when we perform
a computer simulation of a simple recurrnet network.
On the other hand, computational complexity
classes on processor nets has been studied. In[10], Siegelmann and Sontag showed that a classof languages decided by processor nets in polynomial time equals a class of languages decided bybring Machines in polynomial time, and 1058
processors are sufficient in this simulation. Indyk
improved this result and showed that 25 processors are sufficient [7]. Moreover, Balc\’azar et al.
develop further relationships between languages
which are decided by processor nets and othercomplexity classes [3]. The details of the relationships between time complexity classes on processor nets and circuit complexity on nonuniform
are shown in [11].
circuitA mathematical definition of simple recurrent
networks will be given in section 2.1, and we adopt
a cirtain assumption on gates of simple recurrent networks. Then, we define an equivalence
relation between simple recurrent networks andMealy machines which are a finite automata with
output. Our first result is a construction of a
Mealy machine which simulates a simple recurrent network. This result shows that, under ourassumption, simple recurrent networks can only
learn a regular language and the computational
capabillty of simple recurrent networks is not sufficient to recognize natural languages.
Next, we define an equivalence relation between$\mathrm{f}\mathrm{a}\mathrm{m}\mathrm{i}\mathrm{l}\dot{\mathrm{i}}\mathrm{e}\mathrm{s}$189

The outputs of the hidden unit depend on the outputs of the input unit and the context unit, while
the outputs of the output unit only depends on
the outputs from the hidden unit. More formally,

we define a SRN as follows.
Definition 2.1 A

recurrent network is a
7-tuple $\mathcal{E}=(G, I, O, H, C, A, w)$ , where$S\dot{i}mple$

1. $G=(V, E)\dot{i}S$ a directed graph, whereis a finite set of nodes
is divided
into the following four sets of gates: an input $un\dot{i}tI=\{x_{1}, \ldots , x_{n}\}\subseteq V$ , an output unit $O=\{y_{1}, \ldots, y_{m}\}\subseteq V$, a hidden
unit $H=\{h_{1}, \ldots, h_{k}\}\subseteq V$ and a context $un\dot{i}tC=\{c_{1}, \ldots, c_{k}\}$V. Then,$V$$wh_{\dot{i}C}h$$1\mathrm{u}_{\mathrm{i}^{\ovalbox{\tt\small REJECT}\cup \mathrm{t}\mathrm{U}\mathrm{w}}}\iota$$\subseteq$

Figure 1: A simple recurrent network$E=\{(v_{1}, v_{2})|(v_{1}, v_{2})\in I\cross H\cup C\cross H\cup H_{\mathrm{X}}$a set of edges of G. Edges fromtheunit to the context
must be of
the form $(h_{iC_{i}),h_{i}},\in H,$.

$C\cup H\cross O\}\dot{i}S$$h_{\dot{i}}dden$

simple recurrent networks and Moore machines
which are also finite automata with output. Our
second result is a construction of a simple recurrent network which simulates a Moore machine
under our assumption. Therefore, these two constructions show that the computational capabilityof simple recurrent networks is equal to that of finite automata with output under our assumption.
In section 5, we discuss the relationships between the number of states of a finite automatonwith output and the size of a simple recurrent
networks.

$un\dot{i}t$$c_{i}\in C,$ $1\leq\dot{i}\leq k$

2.

numbers, called
unit.

3.

a set of real
output of the context$A=\{A_{1}, \ldots, A_{k}\}\in \mathrm{R}^{k}\dot{i}S$:$in\dot{i}t\dot{i}al$$k$a weight assignment to theE. We denote the weight of an edgeby. We assume that the$h_{i}\in H,$ $c_{i}\in C,$
weight of the edge$w$

$Earrow \mathrm{R}\dot{i}S$

edges$\dot{i}n$$(v_{1},v_{2})$$w(v_{1}, v_{2})$$1\leq$$(h_{i,\mathrm{Q}}),$$i\leq k\dot{i}S\mathit{1}$.

In. this paper, we adopt the following realistic
assumption on gates of simple recurrent networks:

2

Preliminaries

2.1

Simple Recurrent Networks

Assumption 2.1 A $funct\dot{i}on$ computed at eachgate of a simple recurrent network is a $funct\dot{i}on$whose range is a finite set.

recurrent network (SRN) consists of anunit, an output, a hidden unit and acontext(see Figure 1). The hidden unit, thecontext unit and the output unit are sets of gateseach of which computes a function $f[w_{1}, \ldots, w_{m}]$( $x_{1,\ldots,x_{m})}$ :defined byThis means that we can only physically implement a logic gate whose output is a value of finite precision. Rom Assumption 1, for each gate,
there exists a finite set of real numbers which thegate can output. We define a finite ordered set
VAL which contains these real numbers as follows:

A$S\dot{i}mple$$\dot{i}nput$$un\dot{i}t$$un\dot{i}t$$\mathrm{R}^{m}arrow \mathrm{R},$$w_{1},$$\ldots,$if$0$$f[w_{1}, \ldots,w_{m}](x_{1}, \ldots, x_{m})=\{$$\sum n$$w_{m}\in \mathrm{R},$ $m\in \mathrm{N}$wixi

if $0 \leq\sum_{i=1}^{m}w:x:\leq 1$$:_{=}1$

1

VAL$\sum_{i=1}^{m}w:xi<0$

if$\sum_{1=1}^{m}.w:xi>1$

.

where

$=$

{

$val_{k}\in \mathrm{R},$$\mathrm{s}\mathrm{h}\mathrm{a}\mathrm{U}$$\sum_{i=}^{m_{1}}$$\ldots,$$val_{i},$$\ldots$$1\leq k\leq p,$, valj, ...,

$val_{p}$},$0\leq val_{i}<valj$$\leq$

N. In the sequel, we assume
that a gate compute a function $F[ \sum_{i}^{m}=1wiXi]$ :$1,\dot{i}<j,\dot{i},j,$ $k\in$$\mathrm{R}^{m}arrow \mathrm{V}\mathrm{A}\mathrm{L},$For convenience, we
use $F$ [wixi] instead of $f[w_{1}, \ldots, w_{m}](X1, \ldots, xm)$ bom here on.
The context unit of a SRN holds a copy of theoutputs of the hidden unit at a previous time step.

$val_{1},$$m\in \mathrm{N}$.

Now, we define an input sequence and an output sequence of a SRN. For $v\in V,$ $t\geq 0$ , letdenote the output of the gate at time . The
input for a SRN at time , denoted, is the$S_{v}(t)$

$t$

$v$

$t$

$\mathcal{I}(t)$190, where $x_{i}\in I,$
The output of a SRN at, wheretime $t\geq 2$ is the sequence
sequence$S_{x_{1}}(t)\cdots s_{x_{n}}(t)$$\{0,1\},$$1\leq\dot{i}\leq n$$y_{i}\in O,$$1\leq\dot{i}\leq m$$S_{x_{i}}\in$.

$S_{y_{1}}(t)\cdot \mathrm{v}\cdot S_{y_{m}}(t)$.

Definition 2.2 An input sequence with length. For
isand a $SRN$
input sequencewith lengthis, an output sequence of$\mathcal{I}$$\mathcal{I}=\mathcal{I}(0)\mathcal{I}(2)\mathcal{I}(4)\cdots \mathcal{I}(2(n-1))$

$n$

$n$

$\mathcal{I}$$a$$\mathcal{E}$$\mathcal{E}$$\mathcal{O}(2)\mathcal{O}(4)\mathcal{O}(6)\cdots \mathcal{O}(2n)$2.2$T_{\mathcal{E}}(\mathcal{I})$.

Lemma 2.1 For a Mealy machine $M’$ , there exists a Moore machine $M$ which is equivalent to$M’$

Definition 2.3 A Mealy machine $M$ is a 6-tuple, where is a finite set ofstates, $q_{0}\in Q$ is an initial state,is an input
alphabet,
is an output alphabet, :is anis a transition function, and :output function.
$Q$$M=(Q, \Sigma, \Delta, \delta, \lambda, q\mathrm{o})$$\Sigma$$Q\cross\Sigmaarrow Q$$\delta$$\triangle$$\lambda$$Q\cross\Sigmaarrow\Delta$

Let $q(t)\in Q$ denote the state of $M$ at time

. We define an input sequence and an output
sequence of a Mealy Machine as follows:$t$

Definition 2.4 An input sequence of a Mealy, is a string $w=$
machine with length$w$$i\in \mathrm{N}$$0\leq j\leq i-1$.

$M=(Q, \Sigma, \Delta, \delta, \lambda, q\mathrm{o})$

$k$

$l$

$\{a_{0}, \ldots, a_{k}-1\}$$\Delta=\{b_{0}, \ldots, b_{l-}1\}$

Definition 2.8 A state vector of $M$ at time is$v(t)\in\{0,1\}^{km}$ andsatisfies the following properties:
th entry
1. If $t=0$ and $q(t)=q_{i}$ , from theto the $\dot{i}k+kth$ entry of $v(t)$ are all l’s and.
the others are$t$$\dot{i}k+1$$0^{)}s$$w$

2. If $t\neq 0$ and $q(t)=q_{i}$ , only one entry fromthe $ik+1$ th entry to the $\dot{i}k+kth$ entry of $v(t)$.
is 1 and the others are$=$$T_{M}(w)=\lambda(q(\mathrm{O}), a\mathrm{o})\lambda(q(1), a_{1})\cdots\lambda(q(\dot{i}-1), ai-1)$

such that $q(t+1)=\delta$ ( $q(t)$ , at), $0\leq t\leq\dot{i}-1$ .
We define an equivalence relation between simple
recurrent machines and Mealy machines.
is said to be equivalent
Definition 2.6 A
to a Mealy machine $M$ if $T_{\mathcal{E}}(W)=T_{M}(w)$ for any
sequence .
$SRN\mathcal{E}$

2.3

Vector representations

Suppose that the number of states of a Moore
is $m$ , the nummachine
ber of elements of the input alphabet is , andthe number of elements of the output alphabet
is . Namely, let $Q=\{q_{0}, \ldots, q_{m}-1\},$ $\Sigma=$.
andofa Moore maWe first define a state vector
chine. Each entry of a state vector corresponds
to a tuple of a state and an input symbol of a
Moore machine.

Definition 2.5 For an input sequence$a0a_{1}\cdots ai-1$ , an output sequence of a Mealy machine $M,$ $T_{M}(w)$ is a string$\dot{i}nput$.

2.4

A Mealy mach\’ine is a deterministic finite automaton with output $[1, 6]$ .

$a_{0}a_{1}\cdots a_{i-1},$$\grave{s}equence$$=$

Mealy Machines$a_{j}\in\Sigma,$and an output seWe define an input
quence of a Moore machine in the same fashion of
those of a Mealy machine. The following lemma
is known [6].

$w$

Moore Machines

Moore machine is also a deterministic finite
automaton with output [6].
$.\mathrm{A}$$\mathrm{O}’ s$

Next, we define an input vector of a Moore machine. Let $I(t)$ denote a given input symbol of a
Moore machine at time .
$t$Definition 2.9 An input vector of $M$ at timeis $w(t)\in\{0,1\}^{k}$ , and if $I(t)=a_{i}$ , the $i+1$ th.
entry of $w(t)$ is 1 and the others are$t$$\mathrm{O}’ s$

We define a state-input vector based on the above
definitions.

Definition 2.10 Let $v(t)=(v_{1}(t), \ldots, vkm(t))\in$$\{0,1\}^{km}$ a state vector and $w(t)=(w_{1}(t),$,$M$ at time$w_{k}(t))\in\{0,1\}^{k}$ an input vectorof. Then, a state-input vector of $M$ at time
is $V(t)=(v_{1}(t), \ldots, vkm(t), w_{1}(t), \ldots, wk(t))\in$$\ldots$$t$$t$

is a 6-tuple
Definition 2.7 A Moore machine, where is a finite set ofstates, $q_{0}\in Q$ is an initial state,is an input
alphabet,
is an output alphabet, :is anis a transition function, and :$M$$M=(Q, \Sigma, \Delta, \delta, \lambda, q\mathrm{o})$$Q$$\{0,1\}^{km}+k$.

$\Sigma$$\Delta$$\delta$$\lambda$

output function.

$Q\cross\Sigmaarrow Q$$Qarrow\triangle$

Next, we define an output vector of a Moore machine. Let $O(t)$ denote an output symbol of a
Moore machine at time .
$t$

191

for each $1\leq i\leq k$ . Then, the transition
function of $M$ is defined by $\delta(p, \sigma)=p’$
where $p=a_{c_{1}}\cdots a_{c_{k}}\in Q,$
andthe aboveequations.

Definition 2.11 If an output vector $\cdot ofM$ attime $t\dot{i}su(t)\in\{0,1\}^{l}$ , and $O(t)=b_{i}$ , then the$i+1$ th entry of $u(t)$ is 1 and the others are.

$i,$$\delta$$\mathrm{O}’ s$$\sigma=a_{x_{1}}\cdots a_{x_{n}}\in$$\Sigma$

Finally, we give the definition of equivalence
relation between simple recurrent networks andMoore machines.

4. Finally, we construct the output functionof $M$ . Suppose that the output pattern of
the input unit of is, the output pattern of the context unit isand the output pattern of the hidden unit is. The output of depends on the
output pattern of the hidden unit. That is,
the output of the gatesin the output unit
is given by$\lambda$

Definition 2.12 For input sequence $w,$ $\sup-$pose that a Moore machine $M$ yeilds the output
sequence $T_{M}(w)$ and ayeilds the output
sequence. Then, isto be equivalent
to $M$ if $T_{M}(w)=bTg(w)$ for all where is theoutput alphabet for the initial state of $M$ .
$a$$\mathcal{E}$$a_{x_{1}}\cdots a_{x_{n}}$$a_{c_{1}}\cdots a_{c_{n}}$$SRN\mathcal{E}$$T_{\mathcal{E}}(w)$$sa\dot{i}d$$\mathcal{E}$$w$3$p’=a_{h_{1}}\cdots ah_{k}\in Q\mathrm{S}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{s}\mathfrak{g}\Gamma$$\mathcal{E}$$a_{h_{1}}\cdots a_{h_{k}}$$b$$a_{y_{i}}$Constructing Mealy Machines$a_{yi}=F[ \sum_{j=1}^{k}w(h_{j,y_{i})]}ah_{k}$In this section, we will construct a Mealy machine which is equivalent to a given SRN. We describe how to define the states,the transition function and the output function of the SRN.
Suppose that a SRN $\mathcal{E}=(G, I, O, H, C, A, w)$ isgiven, where $|I|=n,$ $|O|=m,$ $|H|=|C|=k$ . We
construct a Mealy machine
which simulates in the following way.

.

Then, the output function of $M$ is definedbywhere $p=a_{c_{1}}\cdots a_{c_{k}}\in Q,$$\lambda$$\lambda(p, \sigma)=\gamma$$a_{x_{1}}\cdots a_{x_{n}}\in\Sigma,$$\sigma=$$\gamma=a_{y_{1}}\cdots a_{y_{m}}\in Q\mathrm{s}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{S}\mathfrak{h}\Gamma$

the above equations.
We have the following result:$M=(Q, \Sigma, \Gamma, \delta, \lambda, q_{0})$Theorem 3.1 Under Assumption 2.1, for any
simple recurrent network , there exists a Mealy
machine $M$ which is equivalent to$\mathcal{E}$$\mathcal{E}$

1. Each state $p\in Q$ of $M$ represents the output
patternof the context unit, where
VAL and. Note that every output pattern of the context unit can be represented as a word in VAL . Thus, the statesof $M$ includes all the repreS.entation of theoutput pattern of the context unit of .
The initial output pattern of the context unitof corresponds to the initial state$ of $M$ .

$\mathcal{E}$.

$a_{c_{1}}\cdots a_{c_{k}}$$\mathrm{q}\in C$$a_{c_{t}}\in$4$k$

In this section, we will show that there exits a
SRN which simulates a Moore Machine. For thispurpose, we use a connection matrix of a Moore
machine [2]. Our first goal is to show that a connection matrix of a Moore machine can be implemented on a SRN. Through this section, consider
a Moore machinewith $Q=$$\{q_{0}, q_{1}, \ldots, qm-1\}$ and $\Sigma=\{a0, a_{1}, \ldots, ak-1\}$ .

$\mathcal{E}$$\mathcal{E}$$q0$

2. Since the number of the gates in the context
unit is equal to that of the hidden unit, eachstate $p\in Q$ of $M$ also represents the output
patternof the hidden unit, where.
and$M=(Q, \Sigma, \Delta, \delta, \lambda, q\mathrm{o})$$a_{h_{1}}\cdots a_{h_{k}}$$h_{i}\in \mathcal{H}$$a_{h_{\mathfrak{i}}}\in \mathrm{V}\mathrm{A}\mathrm{L}$Constructing Simple Recurrent Networks

3. We construct the transition function of $M$ .
Suppose that the output pattern of the input
unit of isand the output patternof the context unit of is. The
output pattern of the hidden unit depends on. That is, the output
andof the gate
in the hidden unit is given by

4.1$\delta$

Connection matrices

We first define a connection matrix of a transition function of a Moore machine [2].

$\mathcal{E}$$a_{x_{1}}\cdots a_{x_{n}}$$\mathcal{E}$$a_{c_{1}}\cdots a_{\mathrm{c}_{n}}$$a_{c_{1}}\cdot*\cdot ac_{k}$Definition 4.1 A connection matrix
tion function of $M$ is$a_{x_{1}}\cdots a_{x_{n}}$$\alpha$of transi-$a_{h_{f}}$$\alpha_{ij}=\{x\in\Sigma|\exists q_{iq_{j}},\in Q, \delta(q_{i}, x)=qj\}$$a_{h_{i}}=F[_{j=1} \sum^{k}w(Cj, h_{i})a_{c}j+\sum_{j=1}^{n}w(Xj, h_{i})axj]$

,

where
is an entry of thecolumn of the matrix .
$\alpha_{ij}$$\alpha$$\dot{i}th$,row and the $jth$192

Weight matrices

4.2

From the definition, a connection matrix ofis an $m\cross m$ matrix. We define a weight matrix

SRN is a finite set, namely VAL $=\{0,1\}$ . Therefore, a function computed at each gate is$\alpha$$M$$\mathrm{o}\mathrm{f}M$.

$F[ \sum_{i=1}^{m}wi^{X]}i=\{$Definition 4.2 For a Moore machine $M$ ,weight matrix
of $M$ is a $km\cross(km+k)$ matrix
following properties:
thewhich satisfies

if
if
1 if

$wixi<0$$0$$\sum_{i=1}^{m}$$0$$0 \leq\sum_{i=1}^{m}$$\sum_{i=1}^{m}$$wixi\leq 1$$wixi>1$ .

$a$$\alpha’$$\bullet F_{or}\dot{i}ifand’ Oj,nly\dot{i}fihereex’,0\leq 1\leq\dot{i},j\leq km_{istSh}iheen\iota ry\alpha_{ij}’\dot{i}S\frac{1}{-1,k+1}h\leq k$.

such thatthe entry
not exist$h,$$\sigma$from the function $F$ .

Definition 4.3 For an $n\cross m$ matrix
tion: $\{0,1\}^{m}arrow\{0,1\}^{n}$ is$A$, a func-$\sigma_{A}$andis if and only if there does
$0\leq h\leq k-1$ , such that$\delta(q_{\lfloor}(i-1)/k\rfloor’ ah)=q_{\lfloor}(j-1)/k\rfloor$$\alpha_{ij}’$

We will define a function’$0$$\delta(q_{\lfloor}(i-1)/k\rfloor’ ah)=q\lfloor(j-1)/k\rfloor$$\sigma_{A}(x)=$ ,.

$1\leq\dot{i}<km$ , $km\leq j\leq km+k$ , the
For
mod
entry
is
if (j-km) mod
is if (j–km) mod $k\neq$
and the entry
mod .
$\dot{i},j,$$k=\dot{i}$$\frac{2k+\overline{1}}{2k+2}$$\alpha_{ij}’$$k$where $x=$$(x_{1}, \ldots , x_{m})$and$\mathit{0}$$\alpha_{ij}’$

$A=$

$k$

$\dot{i}$Now, we construct a weight matrix
nection matrix as follows:$\alpha’\mathrm{h}_{\mathrm{o}\mathrm{m}}$a con-$\alpha$1. Let$\alpha^{T}$

be a transposed matrix of$\alpha$.

2. For an $m\cross m$ matrix of $M$ , let a matrix
be a $km\cross(km+k)$ matrix.

$\alpha’$$\alpha$$\alpha’$as:, a state
Lemma 4.1 Suppose that,
vectorinput
isanvector of the stateof thevectorstate-input
,
and a
is
input symbolofis a state
is V. Then, a vector
andvector of the state .
$\delta(q_{i}, a_{j})=q_{h}$$q_{i}$$a_{j}$

contains a symbol $at\in$,entries in thetheandcolumns
the.
row are all$\alpha_{ij}$$k(j-1)+1\mathrm{t}\mathrm{h},$$k$$k(j-1)+k\mathrm{t}\mathrm{h}$$1)+t\mathrm{t}\mathrm{h}$$\frac{1}{k+1}$

does not contains a sym(b) If the entry,
bol $at\in\Sigma,$ entries in the..., thecolumns and therow are all .
$\alpha_{ij}$$k(j-1)+1\mathrm{t}\mathrm{h}$$k(j-1)+k\mathrm{t}\mathrm{h}$$0$$k(\dot{i}-1)+t\mathrm{t}\mathrm{h}$4. Entries in the 1st, ...,the kmth rows and thecolumns of are, therow, an entry in
defined as follows: for thethe ith row and the $km+$ ( mod ) column
and the other entries are all .
of is$km+1\mathrm{t}\mathrm{h},$$\ldots$$\alpha’$$km+k\mathrm{t}\mathrm{h}$$\dot{i}\mathrm{t}\mathrm{h}$$i$$\alpha’$$\frac{2k+1}{2k+2}$

$k$

$w$

$\sigma_{\alpha’}(V)$$q_{h}$$\ldots$$k(\dot{i}$ -

$k$

$v$

$w$

$v$

$\Sigma,$

4.3

The outputs of units of SRN’s are regarded as
vectors. A transition function of $M$ can be imple.
mented by using a function$\sigma_{\alpha’}$3. Entries in the 1st,...,the kmth rows and theare defined
1st,. .., the kmth columns of(a) If the entry.

$\mathrm{t}\mathrm{h}$$0$Implementing matrices on simple
recurrent networks

In this paper, we already have assume that therange of a function computed at each gate of a

4.4

Constructing simple recurrent networks which simulate Moore ma-chine.

$\mathrm{s}$In this section, we will construct a SRN which isequivalent to a given Moore machine. We describe
how to define the input unit, the output unit, thecontext unit, the hidden unit, the initial output
and the weights.
be a Moore machineLet. and $m=|Q|,$ $k=|\Sigma|$ , and $l=|\Delta|$ . We will construct a SRN $\mathcal{E}=(G, I, O, H, C, A, w)$ as follows:$M=(Q, \Sigma, \Delta, \delta, \lambda, q\mathrm{o})$1. The input unit is $I=\{x_{1}, \ldots, x_{k}\}$ .

2. The output unit is$O=\{y_{1}, \ldots, y\iota\}$.

3. The context unit is $C=\{c_{1}, \ldots, C_{k}m\}$ , andthe hidden unit is $H=\{h_{1}, \ldots, h_{km}\}$ .

193

4. Letbe a state vector of the initial state
and $v(\mathrm{O})=(v_{1}(0), \ldots, vkm(0))$ , where$v_{i}(0)\in\{0,1\},$ $1\leq\dot{i}\leq km.$ Then, the initial output is $A=\{A_{1}, A_{2}, \ldots A_{km}\}$ , where$1\leq i\leq km$ .
$v(\mathrm{O})$6Conclusion$q_{0}$$A$$A_{i}=v_{i}(\mathrm{O}),$

5. Note that he weight matrix
of $M$ is a$km\cross(km+k)$ matrix. We define the weights
as follows:$\alpha’$$t$$xi\in I,$ $h_{j}\in H$ , the(a) For an edge
weightis the entry in therow and $km+1t\mathrm{h}$ column of .
$c_{i}\in C,$ $h_{j}\in H$ , the(b) For a edge
weightis the entry in therow and.
column$(x_{i}, h_{j}),$$w(X_{i}, h_{j})$$j\mathrm{t}\mathrm{h}$$\alpha’$$(c_{i}, h_{j}),$$w(C_{i}, h_{j})$$j\mathrm{t}\mathrm{h}$$\mathrm{f}\alpha’$$\dot{i}\mathrm{t}\mathrm{h}$6. If, the weightis an arbitrary value that is greater than 1 for ,$\dot{i}k\leq s\leq\dot{i}k+k$ .
The weights of the otheredges are all .
We obtain the following theorem.
Theorem 4.1 Under Assumption 2.1, for any
Moore machine $M$ , there exists a simple recurrent network
which is equivalent to $M$ .
$\lambda(q_{i})=b_{j}$In this paper, we show that when the range ofa function computed at each gate of a SRN isa finite set, there exists a Mealy machine which
can simulates the SRN. This result means that,
under our assumption, the computational powerof simple recurrent networks is not exceed hatof finite automata with output, and thus, is not
sufficient to recognize natural languages.
On the other hand, a simple recurrent network
can simulates a Moore machine as we showed in
Section 4.4. From our two results, we have shown$t$that the computational capability of simple recurrent networks is equal to that of finite automata
under our assumption.

$w(h_{s}, y_{j})$$h_{s}$$0$

References
[1]

[2]

$\mathcal{E}_{M}$[3]5

The Size of Simple Recurrent
Networks

In this section, we discuss the relationships between the number of states of automata with output and the size of a SRN. Suppose that a SRN
is equivalnet to automata with output $M$ . Let$K(M)$ be a set of automata which are equivalnet
to $M$ andbe a set of SRN’s which are equivalnet to . For $M$ , let $\phi(M)$ denote a number ofthe states of $M$ . For , letdenote thesize of , where the size of a SRN is the numberof gates of .
Definition 5.1
iselement of $K(M)$$\mathcal{E}$$\mathcal{E}$

[4]
[5]
[6]

[7]

$\mathcal{E}$$M_{\min}$$\phi(M_{\min})=\min\{\phi(M)|M\in K(M)\}$satisfiesisJeffrey L. Elman. Distributed representations, simple
recurrent networks and grammatical structure. Machine Learning, Vol. 7, pp. 195-225, 1991.
J. E. Hopcroft and J. D. Ullman. Introduction to Automata Theory, Langu age and Computation. Reading. Addison-Wesley, MA, 1979.
P. Indyk. Optimal simulation of automata by neural$\mathrm{n}\mathrm{e}\mathrm{t}\mathrm{S}.\mathrm{I}\mathrm{n}\tau heoreiCa\iota^{r_{Atso}}Pocespecfedin\mathit{9}^{so}fhe\mathit{1}\mathit{2}thAnnualSym_{\oint g^{on}}osimc^{t}omputersCience(SAc^{u}s’ \mathit{5})$

[8]

$a$

w.hich satisfies$\mathcal{E}_{\min}$$\mathrm{J}\mathrm{e}\mathrm{f}\mathrm{f}\mathrm{r}_{le}\mathrm{e}\mathrm{L}.\mathrm{E}tivecienC1,\mathrm{m}\mathrm{a}n.\cdot \mathrm{F}\mathrm{i}\mathrm{v}_{0}1\mathrm{l}4,\mathrm{p}\mathrm{p}.1\mathrm{n}\mathrm{d}\mathrm{i}\mathrm{n}\mathrm{g}\mathrm{s}\mathrm{t}\mathrm{r}\mathrm{u}_{21}\mathrm{C}\mathrm{t}\mathrm{u}\mathrm{r}\mathrm{e}\mathrm{i}\mathrm{n}079-1,199.\mathrm{i}\mathrm{t}\mathrm{m}\mathrm{e}$$S\dot{i}Ze(\mathcal{E})$$\mathcal{E}$Definition 5.2$A$$\mathrm{p}\mathrm{l}\mathrm{e}\mathrm{x}\mathrm{i}\mathrm{t}\dot{\mathrm{y}}$$S(\mathcal{E})$$\mathcal{E}$Noga Alon, A. K. Dewdney, and Teunis J. Ott. Efficient simulation of finite automata by neural nets.
Joumal ofAssociaiion for Computing Machinery, Vol.
38, No. 2, pp. 495-514, April 1991.
M. A. Arbib, A. J. Kfoury, and Robert N. Moll.
Basis for Theoretical Computer Science. SpringerVerlag, 1981.
Jose’ L. Balca’zar, Ricard Gavald\‘a, Have T. Siegelmann, and Eduardo D. Sontag. Some structural comaspects of neural computation. In Proceedingsof the IEEE Structure in Complexity Theory Conference, pp. 253-265, San Diego, CA, 1993.
. Congni-$a$element of

.

[9]

which

$S(\mathcal{E})$$S \dot{i}ze(\mathcal{E}_{\min})=\min\{size(\mathcal{E})|\mathcal{E}\in S(\mathcal{E})\}$,

pp. 337-348, New York, April 1995. Springer-Verlag.
, Axel Cleeremans, and DavidJames L.
Servan-Schreiber. Parallel distributed processing: Bridging the gap between human and machine mtelligence. Joumal of Japanese Society of Artificial Intelligence, Vol. 5, No. 1, pp. 3-14, January 1990.
守谷純之介, 西野哲朗. 「単純回帰ネットワークを模倣する mealy 機械の構成法」 電子情報通信学会コンピュ$\mathrm{M}\mathrm{c}\mathrm{C}\mathrm{l}\mathrm{e}\mathrm{n}_{\mathrm{a}\mathrm{n}}\mathrm{d}$.

テーション研究会資料. COMP98-27. 1998.

[10] Have T. Siegelmann and Eduardo D. Sontag. On the.

$\mathrm{c}\circ \mathrm{m}the\mathrm{F}^{\mathrm{u}}iflhA^{\circ}cMWorksh_{\mathit{0}}p_{\mathit{0}}nComputationa\iota^{ee}Lea\mathrm{r}nin^{O}g\mathrm{t}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{n}\mathrm{a}\mathrm{l}\mathrm{P}^{\mathrm{O}}\mathrm{w}\mathrm{e}\mathrm{r}\mathrm{o}\mathrm{f}\mathrm{n}\mathrm{e}\mathrm{u}x\mathrm{a}1\mathrm{n}\mathrm{e}\mathrm{t}\mathrm{S}.\ln ProCding_{S}f$

From the above two construction, we obtain thefollowing theorem.
Theorem 5.1 For $M$ and , there exit constants
and $C’$ such that$\mathcal{E}$$C$$C\log\phi(M_{\min})\leq Size(\mathcal{E}_{\min})\leq C’\phi(Mmin)$.

Theory, Pittsburgh, PA, July 1992.
[11] Have T. Siegelmann and Eduardo D. Sontag. Analog
computation via neural networks. Theoretical Computer Science, Vol. 131, pp. 331-360, 1994.