Theory of neuromata.
A finite automatonthe so-called neuromaton, realized by a finite discrete recurrent neural network, working in parallel computation mode, is considered. Both the size of neuromata (i.e., the number of neurons) and their descriptional complexity (i.e., the number of bits in the neuromaton representation) are studied. It is proved that a constraint time delay of the neuromaton output does not play a role within a polynomial descriptional complexity. It is shown that any regular language given by a regular expression of length n is recognized by a neuromaton with &THgr;(n) neurons. Further, it is proved that this network size is, in the worst case, optimal. On the other hand, generally there is not an equivalent polynomial length regular     expression for a given neuromaton. Then, two specialized constructions of neural acceptors of the optimal descriptional complexity &THgr;(
Introduction
Neural networks [7] are models of computation motivated by our ideas about brain
functioning. Both their computational power and their efficiency have been traditionally
investigated [4, 14, 15, 19, 21] within the framework of computer science.
One less commonly studied task which we will be addressing is the comparison
of the computational power of neural networks with the traditional finite models
of computation, such as recognizers of regular languages. It appears that a finite
This research was supported by GA -
CR Grant No. 201/95/0976.
discrete recurrent neural network can be used for language recognition in parallel
mode: at each time step one bit of an input string is presented to the network
via an input neuron and an output neuron signals, possibly with a constant time
delay, whether the input string which has been read, so far, belongs to the relevant
language. In this way, a language can be recognized by a neural acceptor
(briefly, by a neuromaton). It is clear that the neuromata recognize just the regular
languages [12].
A similar definition of a neural acceptor appeared in [2, 8], where the problem of
language recognition by neural networks has been explored in the context of finite
automata. It was shown in [2] that every m-state deterministic finite automaton
can be realized as a discrete neural net with O(m 3
neurons and that at least
neurons are necessary for such construction. This upper and lower
bound was improved in [6, 8] by showing that \Theta(m 1
neurons suffice and that,
in the worst case, this network size cannot be decreased assuming either at most
O(logm)-time simulation delay [6] or polynomial weights [8]. Moreover, several
experiments to train the (second-order) recurrent neural networks from examples
to behave like deterministic finite automata either for a practical exploitation or
for a further rule extraction have also been done [5, 13, 20, 22] using the standard
neural learning heuristics back-propagation.
In the present paper we relate the size of neural acceptors to the length of regular
expressions that on one hand are known to possess the same expressive power as
finite automata, but on the other hand they represent a tool whose descriptional
efficiency can exceed that of deterministic finite automata.
First, in section 2 and 3, respectively, we will introduce the basic formalism for
dealing with regular languages and neuromata. We will prove that a constant time
delay of the neuromaton output does not play a role within a linear neuromata
size. Therefore, we will restrict ourselves to neuromata which respond only one
computational time step after the input string is read. Then, in section 4 we will
prove that any regular language described by a regular expression of a length n
can be recognized by a neuromaton consisting of O(n) neurons. Subsequently,
in section 5 we will show that, in general, this result cannot be improved because
there is a regular language given by a regular expression of length n requiring neural
acceptors of
n). Therefore, the respective neuromaton construction from a
regular expression is size-optimal. This can be used, for example, for constructive
neural learning when a learning algorithm for regular expressions from example
strings [3] is first employed. On the other hand, in section 6 this construction is
proven not to be efficiently reversible because there exists a neuromaton for which
every equivalent regular expression is of an exponential length.
Next, in section 7 we will present two specialized constructions of neural acceptors
for single n-bit string recognition that both require O(n 1
neurons and either
O(n) connections with constant weights or O(n 1
weights of the size
O(2
The number of bits required for the entire string acceptor description in
both cases is proportional to the length of the string. This means that these automata
constructions are optimal from the descriptional complexity point of view.
They can be exploited as a part of a more complex neural network design, for exam-
ple, for the construction of a cyclic neural network, with O(2 n
neurons and edges,
which computes any boolean function [9].
In section 8 we will introduce the concept of Hopfield languages as the languages
that are recognized by the so-called Hopfield acceptors (Hopfield neuromata) which
are based on symmetric neural networks (Hopfield networks). Hopfield networks
have been studied widely outside of the framework of formal languages, because of
their convergence properties. From the formal language theoretical point of view we
will prove an interesting fact, namely that the class of Hopfield languages is strictly
contained in the class of regular languages. Hence, they represent a natural proper
subclass of regular languages.
Furthermore, we will formulate the necessary and sufficient, so-called, Hopfield
condition stating when a regular language is a Hopfield language. In section 9 we
will show a construction of a Hopfield neuromaton with O(n) neurons for a regular
language satisfying the Hopfield condition. Thus, we will obtain a complete characterization
of the class of Hopfield languages. As far as, the closure properties of
Hopfield languages are concerned, we will show that the class of Hopfield languages
is closed under union, intersection, concatenation and complement and that it is
not closed under iteration.
Finally, in section 10 we investigate the complexity of the emptiness problem
for regular languages given by neuromata or by Hopfield acceptors. We will prove
that both problems are PSPACE-complete. This is a somewhat surprising because
the identical problems for regular expressions, deterministic and non-deterministic
finite automata are known to only be NL-complete [10, 11]. It confirms the fact
from section 6 that neuromata can be stronger than regular expressions from the
descriptional complexity point of view. As a next consequence we will obtain that
the equivalence problem for neuromata is PSPACE-complete as well.
All previous results jointly point to the fact that neuromata present quite an
efficient tool not only for the recognition of regular languages and of their subclasses
respectively, but also for their description. In addition, the above-mentioned constructions
can be generalized for the analog neural networks [18].
A preliminary version of this paper concerning general neuromata and Hopfield
languages, respectively, appeared in [16] and [17].
Regular Languages
We recall some basic notions from language theory [1]. We introduce the definition
of regular expressions which determine regular languages. The concept of a
(deterministic) finite automaton is defined and Kleene's theorem about the correspondence
between finite automata and regular languages is mentioned as well.
An alphabet is a finite set of symbols. A string over an alphabet \Sigma
is a finite-length sequence of symbols from \Sigma. The empty string, denoted by e, is
the string with no symbols. If x and y are strings, then the concatenation of x and
y is the string xy. The string xx
ntimes
is abbreviated to x n . The length of a string
x, denoted by jxj, is the total number of symbols in x.
language over an alphabet \Sigma is a set of strings over \Sigma. Let L 1 and
L 2 be two languages. The language L 1 \Delta L 2 , called the concatenation of L 1 and L 2 , is
g. Let L be a language. Then define
for n - 1. The iteration of L, denoted L ? , is the language L
n=0 L n . Similarly
the positive iteration
Definition 3 The set RE of regular expressions over an alphabet
defined as the minimal language over an alphabet f0;
the following conditions:
1. ;;
2. if ff; fi 2 RE then also (ff
In writing a regular expression we can omit many parentheses if we assume that
? has higher precedence than concatenation and the latter has higher precedence
than +. For example, ((0(1 ? may be written abbreviate the
ntimes
to ff n but jff n j remains n \Delta jffj.
Definition 4 The set is the set of regular languages [ff] which
are denoted by regular expressions ff as follows:
1.
2. if ff; fi 2 RE then [ff
We also use a regular expression ff corresponding to the positive iteration [ff]
Definition 5 A (deterministic) finite automaton is a 5-tuple
where is a finite set of automaton states, \Sigma is an input alphabet (in our
case \Gamma! Q is the transition function, q 0 2 Q is the initial
state of the automaton, and F ' Q is a set of accepting states.
Definition 6 The generalized transition function of the automaton
is defined in the following way:
1.
2.
Fg is the language recognized by the finite automaton
A.
Theorem 1 (Kleene). A language L is regular if f it is recognized by some finite
automaton A (i.e.,
Neuromata
In this section we formalize the concept of a neural acceptor - the so-called neu-
romaton which is a discrete recurrent neural network (or neural network, for short)
exploited for a language recognition in the following way: During the network com-
putation, an input string is presented bit after bit to the network by means of
a single predetermined input neuron. All neurons of the network work in paral-
lel. Following this, with a possible constant time delay the output neuron shows
whether the input string, that has been already read, is from the relevant language.
A similar definition appeared in [2] and [8].
Definition 7 A neural acceptor (briefly, a neuromaton) is a 7-tuple
out; is the set of n neurons including the input neuron inp 2
, and the output neuron out 2 V , is the set of edges,
is the set of integers) is the weight function (we use the abbreviation
Z is the threshold function (the abbreviation
is the initial state of the network.
The graph (V; E) is called the architecture of the neural network N and
is the size of the neuromaton. The number of bits that are needed for the whole
neuromaton representation (especially for the weight and threshold functions) is
called the descriptional complexity of neuromaton.
formally, due to the notational
consistency, by arbitrary xm+l 2 f0; 1g; l - 1, be the input for the neuroma-
ton Further, assume that all oriented paths from
inp to out in the architecture (V; E) have length at least k 1. The
state of the neural network at the discrete time t is a mapping s 1g. At
the beginning of a neural network computation the state s 0 is set to s 0
. Then at each time step
network computes its new state s t from the old state s t\Gamma1 as follows:
otherwise. For the neural acceptor N and
its input x 2 f0; 1g m we denote the state of the output neuron out 2 V in the time
1g is the
language recognized by the neuromaton N with the time delay k.
First, we show with respect to language recognition capabilities that a constant
time delay of the neuromaton output does not play a role, within a linear neuromata
size. More precisely, all languages recognized with the time delay k by a neuromaton
of size n can be recognized with the time delay 1 by a neuromaton of size O(2 k n).
be a neuromaton of size n such that
all oriented paths from inp to out in the architecture (V; E) have length at least
1. Then there exists a neuromaton N
init ) of the size 2 k (n
Proof: The idea of the proof is to construct N ? in such a way that it checks
ahead all possible computations of N for the next steps and cancels all wrong
computations that do not match the actual input being read with the time delay
For this purpose besides the input and output neurons inp ? , out ? , the neuroma-
ton N ? consists of 2 k blocks N x which foresee the computation of N ,
each of them for one of the possible next k bits x of input. Denote neurons in these
blocks in the same way as in N but each of them indexed by the relevant k bits.
Then the state of the neuron v x of N ? is equal to the state of the neuron v 2 V of
N after the computation over the next bits (i.e., over the first k \Gamma 1 bits
of x 2 f0; 1g k ) is performed. This is achieved as follows.
The block N yb where y 2 f0; 1g its new state from the
old state of the block N ay where a 2 f0; 1g. Therefore neurons in N ay are connected
to neurons of N yb and the corresponding edges are labeled with relevant weights
with respect to the original weight function w of N . The block N yb has the constant
input b which is taken into account by modifying all thresholds of neurons in this
block, especially when
The input bit c 2 f0; 1g of N ? indicates that the computations of N ay , where
a 6= c, are not valid. Therefore the input neuron inp ? cancels these computations
by setting all neuron states in N ay to zero. Thus, all neurons in 2 k\Gamma1 blocks N ay
states when the previous input bit does not match a.
This also enables the block N yb to execute the correct computation because the
influence of one invalid block from either N 0y or N 1y which are connected to N yb ,
is suppressed, due to zero states.
The neurons in the blocks N x which are connected to out x lead to the output
neuron out ? as well. They are labeled with the same weights. We know that half of
them do not have any influence on out ? . Moreover, among the remaining ones, the
corresponding neurons v x (v 2 V ) from all blocks N x have the same
state because the distance between inp and out in N is at least k and the last k
input bits cannot influence the output. It is sufficient to multiply the threshold of
out ? by 2 k\Gamma1 in order to preserve the function computed by out. In this way, the
correct recognition is accomplished with lookahead.
A formal definition of the neuromaton N
follows:
ay
ay
init (v ya
where s k\Gamma1 (v)(y) is the state of neuron v in the neuromaton N for the input y 2
1g k\Gamma1 at the time step k \Gamma 1.
The term bw(hinp; vi) in the threshold definition takes into account the weight
of the constant input in the block N y1 (y 2 f0; 1g corresponding to the original
weight associated with the edge leading from the input inp to the relevant neuron v
in the neuromaton N . The definition of w ensures setting the states of
all neurons in the block N 0y (y 2 f0; 1g k\Gamma1 ) to zero iff the input inp ? is 1. Similarly
the definition of weights w together with the term aw ? (hinp
in the threshold definition cause zero states of all neurons in the block N 1y (y 2
Clearly, the size of the neuromaton N ? is 2. 2
Following Lemma 1, we can restrict ourselves to neuromata which respond only
one computational time step after the input string is read because their size is, up
to a constant multiplication factor, as large as the size of the equivalent neuromata
with a constant time delay. Therefore, in the rest of this paper we will assume
that the time delay in the neuromaton recognition is 1 and that any neuromaton
architecture does not contain an edge from the input to the output neuron. We will
also denote L 1 (N ) by L(N ) for any neuromaton N .
Next, we will prove that the neural acceptor can be viewed as a finite automaton
[12] and therefore, neuromata recognize exactly regular languages due to Theorem
1.
Theorem 2 Let language recognized by some neuromaton N . Then
L is regular.
Proof: Let neural acceptor. We define a
deterministic finite automaton
\Sigmag and q . The transition function is defined
for s 2 Q and x 2 \Sigma as follows:
Finally, \Sigmag. Then the proposition
follows from Theorem 1. 2
4 Upper Bound
We show that any regular language, given by a regular expression of length n,
may be recognized by a neuromaton of size O(n). The idea of recognition by
neuromaton is to compare an input string with all possible strings generated by the
regular expression and to report via the output neuron whether some of these strings
match the input. Therefore, the constructed architecture of the neural network
corresponds to the structure of the regular expression. The neuromaton proceeds
through all oriented network paths that correspond to all strings generated by this
expression and that, at the same time, match the part of the input string that has
been read so far.
Theorem 3 For every regular language L 2 RL denoted by a regular expression
there exists a neuromaton N of the size O (jffj) such that L is recognized
by N (i.e.,
Proof: Let be a regular language denoted by a regular expression ff.
We construct a neuromaton N O (jffj) so that
We first build an architecture (V; E) of the neural network N ff recursively with
respect to the structure of the regular expression ff. For that purpose we define the
sequence of graphs corresponding
to the whole expression ff which is recursively partitioned into shorter regular
subexpressions, so that (V corresponding only to the elementary
subexpressions 0 or 1 of ff (we say, vertices of the type 0 or 1). For the sake of
notational simplicity we identify the subexpressions of ff with the vertices of these
graphs.
1.
2. Assume that have already been constructed and
a subexpression of ff different from 0 or 1. Hence, besides the empty language
and the empty string, the regular expression fi can denote union, concatena-
tion, or iteration of subexpressions of fi. With respect to the relevant regular
operation the vertex fi is fractioned and possibly new vertices corresponding
to the subexpressions of fi arise in the graph (V To be really
rigorous we should first remove the vertex fi and then add the new vertices.
However, due to the notational simplicity we do not insist on such rigor and
therefore, we can identify one of the new vertices with the old fi. That is why
we write rather inexactly, for example, 'fi has the form fi fl'. Moreover, we
ffl fi is ;: V g.
ffl fi is e: V
fiigg.
ffl fi has the form fi
g.
ffl fi has the form fi
g.
ffl fi has the form fiig.
This construction is finished after contains only subexpressions
0 or 1. Then we define the network architecture in the following way:
For Now we can define the weight
function w and the threshold function
is the neuron of type 1:
is the neuron of type 0:
The initial state is defined as s 0
The set V contains three special neurons inp; out; start, as well as, other neurons
of the type 0 or 1 - one for each subexpression 0 or 1 in ff; hence, jV
An example of the neuromaton for the regular language [(1(0
figure 1 (the types of neurons are depicted inside the circles representing neurons;
thresholds are depicted as weights of edges with constant inputs \Gamma1).
inp
start 101
out
Figure

1: Neuromaton for [(1(0
We prove that From the construction of (V
above, it is easy to observe that this graph corresponds to the structure of the
regular expression ff. This means that for every string
there is an oriented path start out leading from
to out 2 V p and containing the vertices of the relevant types (0 or 1).
On the other hand, for any such path there is a corresponding string in L.
The neural acceptor N ff passes through all possible paths that match the network
input. In the beginning the only non-input neuron start 2 V is active (its state is
1). It sends a signal to all connected neurons and subsequently becomes passive (its
state is 0) due to the dominant threshold. The connected neurons of the type 0 or
1 compare their types with the network input and become active only when they
match, otherwise they remain passive. Due to the weight and threshold values, it
follows that any neuron of the type 1 becomes active iff inp 2 V is active and at
least one of j 6= inp, hj; ii 2 E, is active, and any neuron of the type 0 becomes
active iff inp 2 V is passive and at least one of j 6= inp, hj; ii 2 E, is active. This
way all relevant paths are being traversed, and their traverse ends in the neuron
which realizes the logical disjunction, and is active iff the prefix of the
input string, that has been read so far, belongs to L. This completes the proof that
5 Lower Bound
In this section we show the lower
n) for the number of neurons that, in
the worst case, are necessary for the recognition of regular languages which are
described by regular expressions of the length n. As a consequence, it follows that
the construction of the neuromaton from section 4 is size-optimal.
The standard technique is employed for this purpose. For a given length of
regular expression we define a regular language and the corresponding set with an
exponential number of prefixes for this language. We prove that these prefixes
must bring any neuromaton to an exponential number of different states in order
to provide a correct recognition. This will imply the desired lower bound.
Definition 9 For we denote by Ln , \Pi k , and Pn , respectively, the
following regular languages:
hi
It is clear that Pn , n - 1 is the set of prefixes for the language Ln . We prove
several lemmas concerning properties of these regular languages. The regular expression
which defines the language Ln in Definition 9 is in fact of O
length
because the abbreviation for a repeated concatenation is not included when determining
its length. Therefore, we first show that there is a regular expression ff n , of
the linear length only, denoting the same language Ln . The number of prefixes in
Pn is shown to be exponential with respect to n.
Proof:
(i) In the regular expression which denotes the language Ln from Definition 9, we
can subsequently factor out (n \Gamma times the subexpression 1(e + 0) to obtain
the desired regular expression
of the linear length jff which defines the same language
(ii) It follows from Definition 9 that j\Pi k
The following lemma shows how the prefixes in Pn can be completed to strings
from Ln .
Lemma 3
Proof:
(i), (ii) follow from Definition 9.
(iii) Assume . The language Ln is defined via iteration in Definition 9.
Henceforth, we can write
\Pi
Now we prove that any two different prefixes from Pn can be completed by the same
suffix, so that one of the resulting strings is in Ln while the other one is not.
Lemma
Proof: Assume x . Then there exist
We will distinguish two cases:
Without loss of generality, suppose n ?
From (ii) Lemma 3 we obtain x 1
due to (ii) Lemma 3.
2.
We can write x
fe; 0g, for g. Without loss of generality
a
ffl Denote z
\Pi From (i) Lemma 3 z 1 0 2 Ln and z 2 1 2 Ln from (ii) Lemma 3.
This implies that x 1 because Ln is closed under concatenation

. To the contrary suppose that x 2
exist. Hence, z
from (ii) Lemma 3 it follows z
which is a contradiction.
Thus, x 2 y 62 Ln . 2
Now we are ready to prove the following theorem concerning the lower bound.
Theorem 4 Any neuromaton N that recognizes the language
at
n) neurons.
Proof: The neuromaton N , that recognizes the language
must
different states which are reached when taking input
prefixes from Pn because any different x can be completed by y from
Lemma 4, so that x 1 y 2 Ln and x 2 y 62 Ln . This implies that N
needs\Omega\Gamma n) binary
neurons. 2
6 Neuromata Are Stronger
Although from the results of sections 4, 5 it seems that from the descriptional complexity
point of view, neuromata and regular expressions are polynomially equiva-
lent, in this section, we will show that there exists a neuromaton for which every
equivalent regular expression is of an exponential length. This means that the neu-
romata construction from regular expressions that has been described in section 4
is not efficiently reversible.
Theorem 5 For every n - 1 there exists a regular language Ln recognized by a
neuromaton Nn of size O(n) and of descriptional complexity O(n 2 ) such that any
regular expression ff n which defines
We define the finite language to be the set of all
binary strings of length m.
The neuromaton recognizes Ln is a binary
n-bit counter which accepts the input string iff its length is m. The neuron
corresponding to the ith bit of the counter should change its state iff
1. However, the corresponding Boolean function cannot
be computed by only one neuron and, therefore, a small subnetwork of three
neurons a introduced for this purpose. Then v i is a disjunction of a i and b i
where a
and at least one of v its state as required but
it takes two computational steps. This means that the counter is two times slower
and only are required to count till m. Moreover the neuron v 0 generates
the binary sequence (0011) ? and a special neuron rst is introduced to suppress the
firing of the output neuron v n\Gamma2 after m bits are read.
A formal definition of the counter follows:
Clearly, the size of Nn is of order O(n) and its descriptional complexity is O(n 2 ).
Let ff n be a minimal length regular expression which defines the language
We prove that jff n m). The expression ff does not contain
iterations because it defines the finite language (the part containing iterations would
denote the empty language and, thus, could be omitted). To generate strings from
the expression ff n is to be read from the left to the right side without any
returning since no iteration is allowed. But any string of Ln is of length m and that
is why ff n must contain at least m symbols from f0; 1g. Hence jff
Theorem 5 shows that, in some sense, there is a big gap between the descriptive
power of regular expressions and that of neuromata. We will discuss this issue later
in sections 10, 11.
7 Neural String Acceptors
The previous results showed that neuromata have the descriptive capabilities of
regular expressions. In this section we will study how powerful they are when we
confine ourselves to a certain subclass of regular expressions. Here, we will deal with
the simplest case only considering fixed binary strings from f0; 1g ? . We present two
constructions of neural acceptors for a single string recognition. For n-bit strings
they both require O(n 1
neurons and either O(n) connections with constant weights
or O(n 1
weights of the O(2
The number of bits required for
the entire string acceptor description is in both cases proportional to the length of
the string. This means that these constructions are optimal from their descriptional
complexity point of view.
Studying this elementary case is useful because single string recognition is very
often a part of more complicated tasks. The techniques developed for the architectural
neural network design can, for example, sometimes improve the construction
of neuromata from section 4, when a regular expression consists of long binary sub-
strings. The other example of application is a constructive neural learning, where
strings are viewed as training patterns, and the resulting network is composed of
neural acceptors for these strings that work in parallel.
Theorem 6 For any string a = a an 2 f0; 1g n there exists a neural acceptor
of the size O(n 1
neurons with O(n) connections of constant weights. Thus, the
descriptional complexity of the neuromaton is \Theta(n).
Proof: For the sake of simplicity suppose first that positive integer
p. The idea of the neural acceptor construction is to split the string a 2 f0; 1g n
into p pieces of the length p and to encode these p substrings using p 2 (for each p)
binary weights of edges leading to p comparator neurons c . The input string
being gradually stored per p bits into p buffer neurons
. When the buffer is full, the relevant comparator neuron c i compares
the assigned part of the string a with the corresponding part of the
input string x that is stored in the buffer and sends the
result of this comparison to the next comparator neuron. The synchronization of
the comparison is performed by 2p clock neurons, where neurons s tick at
each time step of the network computation, and neurons tick once in a
period of p such steps. The last comparator neuron c p represents the output neuron
and reports at the end whether the input string x matches a.
A formal definition of the neuromaton for the
recognition of the string a follows (see also figure 2). Define
Denote by d
fi fi . Then put
ae
All remaining weights and thresholds are set to 1. Finally, the initial state is
'i
'i
'i
'i
'i
'i
'i
'i
'i
'i
'i
'i x
'i
'i
Z Z Z Z Z Z Z Z Z Z Z Z Z
Z Z Z Z Z Z Z Z Z Z Z Z Z
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
Z Z
Z Z Z
Z Z Z
Z Z Z
Z Z
Z Z Z
Z Z Z
Z Z Z
ae
ae
ae
ae
ae
ae
ae
ae
ae
ae
ae
ae
ae
ae
ae
ae
ae
ae
ae
ae
ae
ae
ae
ae
\Omega \Omega \Omega \Omega \Omega \Omega \Omega \Omega \Omega \Omega \Omega \Omega \Omega \Omega \Omega \Omega \Omega \Omega
inp
out
sp
start

Figure

2: Architecture for a neural string acceptor with O(n) edges.
Note that the weights w are not constant as
required. It is due to the neuron c i which should keep its state 1 after it becomes
active in order to transfer the possible positive result of the comparison to the
next comparator neuron. Therefore, the relevant feedback must exceed the sum of
all other inputs to achieve the threshold value. This can be avoided by inserting
auxiliary neurons, that remember the result of preceding comparisons, between
neighbor comparator neurons. All of these neurons have a constant feedback because
they only have one input, from the previous comparator neuron, to be exceeded.
The construction of the neural acceptor can also be easily adapted for
p. The technique from the proof of theorem 3 is employed for the recognition
of the last r bits of the string a. The resulting architecture of size O(r) is then
connected to the neural string acceptor by identifying the neuron start with the
above-mentioned neuron
'i
'i
'i
'i
'i
'i
'i
'i
'i
x
'i
'i
'i
'i
'i
'i
'i
'i
'i
'i
'i
'i
'i
Z Z Z Z Z Z Z Z Z Z Z Z Z
Z Z Z Z Z Z Z Z Z Z Z Z Z
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
Z
Z Z Z
Z Z Z
Z Z Z
Z
Z
Z Z Z
Z Z Z
Z Z Z
Z
ae
ae
ae
ae
ae
ae
ae
ae
ae
ae
ae
ae
ae
ae
ae
ae
ae
ae
ae
ae
ae
ae
ae
ae
\Omega \Omega \Omega \Omega \Omega \Omega \Omega \Omega \Omega \Omega \Omega \Omega \Omega \Omega \Omega \Omega \Omega \Omega l
l
l
l

Z Z
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
start
out
an
a q+3
a q+2
a q+1
inp
reset
sp

Figure

3: Architecture for a neural string acceptor with O(n 1
Theorem 7 For any string a 2 f0; 1g n there exists a neural acceptor of the size
neurons with O(n 1
weights of the size O(2
Thus, the descriptional
complexity of the neuromaton is \Theta(n).
Proof: The design of the desired neural acceptor is very similar to the construction
from the proof of Theorem 6, except that the number of comparator neurons is
reduced to two neurons c - ; c - . In this case the substrings a
are encoded by O(p) (each by 2) weights of the size O(2 p ) corresponding to
the connection leading from the clock neurons m i to these comparison neurons. The
contents of the input buffer, viewed as a binary number, are first converted into an
integer. This integer is then compared with the relevant encoded part of the string a
by the comparator neuron c - to see whether it is smaller or equal. At the same time,
it is compared by the comparator neuron c - to see whether it is greater or equal.
The neuron which realizes the logical conjunction of comparator outputs is added to
indicate whether the part of the input string matches the corresponding part of the
string a. However, this leads to one more computational step of the neural acceptor.
The correct synchronization can be achieved by exploiting the above-mentioned
additional architecture for the recognition of the last r bits a q+1 ; a
of the string a. Details of the synchronization are omitted, as well as, a
complete formal definition of the neural string acceptor. We only give the definition
of the weights that are relevant for the comparisons:
2 p\Gammaj a (i\Gamma2)p+j for
The weights w are defined as differences
because all clock neurons are active just when the part
of the input is in the buffer. The architecture of the neural string
acceptor is depicted in figure 3 (instead of the above-mentioned conjunction, the
neuron reset is added to realize the negation of comparator conjunction to possibly
terminate the clock). 2
Piotr Indyk [9] pointed out that the latter string acceptor construction from
Theorem 7 can also be exploited for building a cyclic neural network, with O(2 n
neurons and edges, which computes any boolean function. In this case the binary
vector of all function values is encoded into the string acceptor. The position of the
relevant
-bit part of this vector which includes the desired output is given by the
first nbits of input. All possible corresponding 2 n
-bit substrings are generated and
presented to the acceptor to achieve the relevant part of the function value vector
from which the relevant bit is extracted. Its position is determined from the last nbits of input.
8 Hopfield Languages
In section 7 we have restricted ourselves to a special subclass of regular expres-
sions. In this section we will concentrate on a special type of neural acceptors,
the so-called Hopfield neuromata which are based on symmetric neural networks
(Hopfield networks). In these networks the weights are symmetric and therefore,
the architecture of such neuromata can be seen as an undirected graph.
Hopfield networks have been traditionally studied [4, 21] and used, due to their
favorite convergence properties. These networks are also of particular interest,
because their natural physical realizations exist (e.g. Ising spin glasses, 'optical
computers'). Using the concept of Hopfield neuromata, we will define a class of
Hopfield languages that are recognized by these particular acceptors.
The neuromaton that is based on
symmetric neural network (Hopfield network) where hi;
called a Hopfield acceptor (Hopfield
neuromaton). The language recognized by Hopfield neuromaton N is
called Hopfield language.
First, we will show that the class of Hopfield languages is strictly contained
within the class of regular languages. For this purpose we will formulate the necessary
condition - the so-called Hopfield condition when a regular language is a
Hopfield language. Intuitively, Hopfield languages cannot include words with those
potentially infinite substrings which allow the Hopfield neuromaton to converge and
to forget relevant information about the previous part of the input string which is
recognized. The idea of the proof is to find a necessary condition to prevent a
Hopfield neuromaton from converging.
Definition 11 A regular language L is said to satisfy a Hopfield condition if f
for every
Theorem 8 Every Hopfield language satisfies the Hopfield condition.
Proof: Let be a Hopfield language recognized by the Hopfield neuro-
ng and define
be the integer
vectors of size n \Theta 1 and let \Gammafinpg be the integer matrix of size
n \Theta n. Note that the matrix W is symmetric, since N is the Hopfield acceptor.
Let us present an input string v 1 x
to the acceptor N . For a sufficiently large m 0 , the network's computation must
start cycling over this input because the network has only 2 n+1 of possible states.
be the different states in this cycle and x
be the corresponding input bits, so that the state s i is followed by the state s -(i) ,
is the index shifting permutation:
be the inverse permutation of -, and let - r
be the composed permutations, for any r - 1. Further, let ~c
be the binary vectors of size n \Theta 1. Then ( ~
follows from Definition 8.
For each state of the cycle we define an integer
and the symbol T denotes the transposition of a vector. Obviously,
p. Using the fact that the matrix W is symmetric
we obtain
Moreover, x 2. So we can write
~
We know that ( ~
Therefore, (~c T
which implies
p. But from E - p
Then we cannot have both c - 2 n, at the same
time because in this case the inequality of (~c T
is strict. The complementary case of c - 2 simultaneously is
impossible as well. Since then, the number of 1's in ~c - 2 (i) would be greater than
the number of 1's in ~c i for
Therefore, we can conclude that ~c - 2 consequently
This implies that the cycle length p - 2. Hence, for every v 2 2 f0; 1g ? either
This completes the proof
that L satisfies the Hopfield condition. 2
For example, it follows from Theorem 8 that the regular languages [(000) ?
are not Hopfield languages because they do not satisfy the Hopfield condition.
9 The Hopfield Condition Is Sufficient
In this section we will prove that the necessary Hopfield condition from Definition 11,
stating when a regular language is a Hopfield language, is sufficient as well. A
construction of a Hopfield neuromaton is shown for a regular language satisfying
the Hopfield condition.
Theorem 9 For every regular language satisfying the Hopfield condition
there exists a Hopfield neuromaton N of the size O (jffj) such that L is recognized
by N . Hence, L is a Hopfield language.
Proof: The architecture of the Hopfield neuromaton for the regular language
[ff] satisfying the Hopfield condition is given by the general construction from the
proof of Theorem 3. As a result we obtain an oriented network N 0 that corresponds
to the structure of the regular expression ff where each neuron n s of N 0 (besides
the special neurons inp, out, start) is associated with one symbol s 2 f0; 1g from
ff (i.e., is of the type s). The task of n s is to check whether s agrees with the input
bit.
We will transform N 0 into an equivalent Hopfield network N . Supposing that
ff contains iterations of binary substrings with at most two bits, the standard technique
[15, 21] of the transformation of acyclic neural networks to Hopfield networks
can be employed. The idea consists in adjusting weights to prevent propagating a
signal backwards while preserving the original function of neurons. The transformation
starts in the neuron out, it is carried out in the opposite direction to oriented
edges and ends up in the neuron start. For a neuron whose outgoing weights have
been already adjusted, its threshold and incoming weights are multiplied by a sufficiently
large integer which exceeds the sum of absolute values of outgoing weights.
This is sufficient to suppress the influence of outgoing edges on the neuron. After
the transformation is accomplished all oriented paths leading from start to out are
labeled by decreasing sequences in weights.
The problem lies in realizing general iterations using only the symmetric weights.
Consider a subnetwork I of N 0 corresponding to the iteration of some substring of
ff. Let the subnetwork I have arisen from a subexpression fi + of ff in the proof
of theorem 3. After the above-mentioned transformation is performed, any path
leading from the incoming edges of I to the outgoing ones is labeled by a decreasing
sequence of weights in order to avoid the backward signal from spreading. But the
signal should be propagated from any output of the subnetwork I back to each sub-network
input, as the iteration requires. On one hand, an integer weight associated
with such a connection should be small enough in order to suppress the backward
signal propagation. On the other hand, this weight should be sufficiently large
enough to influence the subnetwork input neuron. Clearly, these two requirements
are contradictory.
Consider a simple cycle C in the subnetwork I consisting of an oriented path
passing through I and of one backward edge leading from the end of this path (i.e.,
the output of I) to its beginning (i.e., the input of I). Let the types of neurons in the
cycle C establish an iteration a + where a 2 f0; 1g ? and jaj ? 2. Moreover, suppose
that x 2 f0; 1g 2 and a = x k for some k - 2. In the Hopfield condition set v 2 to
be a postfix of L associated with a path leading from C to out. Similarly set v 1 to
be a prefix of L associated with a path leading from start to C such that for every
which contradicts the Hopfield
condition. Such prefix v 1 exists because, otherwise, the cycle C could be realized
as an iteration of two bits. Therefore a 6= x k . This implies that strings a i ,
contain a substring of the form by - b where b; b. Hence, the string
a has the form either
For notational simplicity we confine ourselves to the former case while the latter
remains similar. Furthermore, we consider a = a 1 by - ba 2 with a minimal ja 2 j.
We shift the decreasing sequence of weights in C to start and to end in the neuron
n y while relevant weights in N 0 are modified by the above-mentioned procedure to
ensure a consistent linkage of C within N 0 . For example, this means that all edges
leading from the output neuron of I in C to the input neurons of I are evaluated by
sufficiently large weights to realize the corresponding iterations. Now the problem
lies in signal propagation from the neuron n b to the neuron n y . Assume
To support the small weight in the connection between n b and n y a new neuron
id that copies the state of the input neuron inp is connected to the neuron n y via
a sufficiently large weight which strengthens the small weight in the connection
from n b . Obviously, both the neuron n b (b = 1) and the new neuron id are active
at the same time and both enable the required signal propagation from n b to n y
together. On the other hand, when the neuron n- b ( - active, the neuron id
is passive due to the fact that it is copying the input. This prevents the neuron n y
from becoming active at that time.
However, for some symbols b in ff there can be neurons n b 0 outside
the cycle C (but within the subnetwork I) to which the edges from n y lead. This
situation corresponds to y being concatenated with a union operation within fi. In
this case the active neurons n b 0 , id would cause the neuron n y to fire. To avoid
this, we add another new neuron n y 0 that behaves identically as the neuron n y for
the symbol y 1g. Thus, the same neurons that are connected to n y are
linked to n y 0 and the edges originally outgoing from n y to n b 0 for all corresponding
b 0 are reconnected to lead only from n y 0 .
A similar approach is used in the opposite case when above-described
procedure is applied for each simple cycle C in the subnetwork I corresponding to
the iteration fi + . These cycles are not necessarily disjoint, but the decomposition
of a = a 1 by - ba 2 with minimal ja 2 j ensures their consistent synthesis. Similarly, the
whole transformation process is performed for each iteration in ff. In this case
some iteration can be a part of another iteration and the magnitude of weights in
the inner iteration will need to be accommodated to embody this into the outer
iteration. It is also possible that the neuron id has to support both iterations in the
same point. Finally, the number of simple cycles in ff is O (jffj). Hence, the size of
the resulting Hopfield neuromaton remains of order O (jffj).
In figure 4 the preceding construction is illustrated by an example of the Hopfield
neuromaton for the regular language [(1(0
A simple cycle consisting of neurons clarified here in details. Notice
the decreasing sequence of weights (7,5,1) in this cycle, starting and ending in the
neuron n y , as well as, the neuron id which enables the signal propagation from n b
to n y . The neuron n y 0 , identical with n y , has also been created because the neuron
originally connected to n y (see figure 1). 2
start
inp
id
id
out

Figure

4: Hopfield neuromaton for [(1(0
Corollary 1 Let L be a regular language. Then L is a Hopfield language if f L
satisfies the Hopfield condition.
Finally, we will briefly investigate the closure properties of the class of Hopfield
languages.
Theorem 10 The class of Hopfield languages is closed under union, concatenation,
intersection, and complement. It is not closed under iteration.
Proof: The closeness of Hopfield languages under union and concatenation follows
from Corollary 1. To obtain the Hopfield neuromaton for the complement, negate
the function of the output neuron out by multiplying the associated weights (and the
threshold) by -2 and by adding 1 to the threshold. Hence, the Hopfield languages
are closed under intersection as well. Finally, due to Theorem 9, [1010] is a Hopfield
language, whereas [(1010) ? ] is not a Hopfield language because it does not satisfy
the Hopfield condition from Theorem 8. 2
Emptiness problem
In order to further illustrate the descriptional power of neuromata we investigate
the complexity of the emptiness problem for regular languages given by neuromata
or by Hopfield acceptors. We will prove that both problems are PSPACE-complete.
Definition 12 Given a (Hopfield) neuromaton N , the (Hopfield) neuromaton emptiness
problem, which is denoted NEP (HNEP), is the issue of deciding whether the
language recognized by the (Hopfield) neuromaton N is nonempty.
Theorem 11 NEP, HNEP are PSPACE-complete.
Proof: To show that both NEP; HNEP 2 PSPACE, an input string for the
(Hopfield) neuromaton N is being guessed bit by bit and its acceptance is checked
by simulating the network computation in a polynomial space to witness the non-emptiness
of
Next, we show that NEP is PSPACE-hard. Let A be an arbitrary language
in PSPACE. For each x 2 f0; 1g ? we will, in a polynomial time, construct the
corresponding neuromaton N such that x 2 A iff N 2 NEP . Further, let M be a
polynomial space bounded Turing machine which recognizes A. First, a cyclic neural
network N 0 which simulates M can be constructed in a polynomial time using the
standard technique [4]. The idea of this construction is that for each tape cell of
M there is a subnetwork which simulates a tape head when it is in this position
during the computation (i.e., the local transition rule). The neighbor subnetworks
are connected to enable the head moves. The input x for M is encoded in the initial
state of N 0 and at the end of the neural network computation one neuron of N 0 ,
called result, signals whether x 2 A. The neural network N 0 is embodied into the
neuromaton N as follows. The input neuron inp of N is not connected to any other
neuron and the output neuron out of N is identified with the neuron result of N 0 .
accepts x iff the neuron out is active at the end of the
simulation iff L(N ) contains all words of the length which is equal to the length
of the computation of M on x iff N 2 NEP . Thus, x 2 A iff N 2 NEP . This
completes the proof that NEP is PSPACE-complete.
For the Hopfield neuromata a similar simulation of M can be achieved using
the symmetric neural network N 0 . It is because any convergent computation of an
arbitrary asymmetric neural network can be simulated by a symmetric network of
a polynomial size [4] and we can assume, without loss of generality, that M stops
for every input. Hence, HNEP is PSPACE-complete as well. 2
Theorem 11 is a somewhat surprising because the identical problems for regular
expressions, deterministic and non-deterministic finite automata are known to only
be NL-complete [10, 11]. In some sense this shows that there is a big gap between
the descriptive power of regular expressions and that of neuromata and confirms
the result from section 6. We will discuss this issue later in section 11.
The difference between the descriptive power of regular expressions and of neu-
romata can also be illustrated by the complement operation. While the emptiness
problem for the complement of the regular expression becomes PSPACE-complete
[1] the emptiness problem complexity of the complement of a neuromaton
does not change because the output neuron can be easily negated.
As a next consequence we will show that the neuromaton equivalence problem
is PSPACE-complete as well.
Given two (Hopfield) neuromata N 1 , N 2 the (Hopfield) neuromaton
equivalence problem which is denoted NEQP (HNEQP) is the issue of deciding
whether the languages recognized by these (Hopfield) neuromata are the same, i.e.
whether
Corollary 2 NEQP, HNEQP are PSPACE-complete.
Proof: To prove that NEQP 2 it is sufficient to show
that its complement is in PSPACE. For this purpose an input string for the neuro-
mata being guessed and its acceptance for one of these two neuromata and
its rejection for the other one are checked by simulating both network computations
in a polynomial space to witness the non-equivalence L(N 1
To show that NEQP is PSPACE-hard, the complement of NEP denoted co-NEP,
which is PSPACE-complete as well, is in a polynomial time reduced to NEQP.
Let the neuromaton N be an instance of co-NEP. We will in a polynomial time
construct the corresponding instance N 1 , N 2 for NEQP so that L(N ) is empty iff
The neuromaton N 1 is identified with N . Let N 2 be an arbitrary
small neuromaton which recognizes the empty language. It is easy to see that
this is a correct reduction. Hence, NEQP is PSPACE-complete. The PSPACE-completeness
of HNEQP can be achieved similarly. 2
Conclusions
In this paper we have explored an alternative formalism for the regular language
representation, based on neural networks. Comparing the so-called neuromata with
the classical regular expressions we have obtained the result that within a polynomial
descriptive complexity, the non-determinism, which is captured in the regular
expressions, can be simulated in a parallel mode by neuromata which have a deterministic
nature.
In our opinion, the descriptive power of the neuromata consists in an efficient
encoding of the transition function. While the transition function of the deterministic
(nondeterministic) finite automata is usually specified by the list of its values
(old state, input symbol)/new state, the same function in the neuromata is given
by the vector of formulae - each for one neuron which evaluates it. This encoding
can be interpreted more like a general program. From this point of view it
is easy to observe that the table of transition rules in the deterministic finite automata
is a special case of such program. Moreover, the neuromata can encode the
nondeterministic transition function efficiently using parallelism. In this way, the
behavior of the neuromata in the exponential number of all possible states can be
described in a polynomial size. However, this process is not reversible. The neural
transition program cannot be generally rewritten as a polynomial size table or a
polynomial length regular expression. Moreover, the number of neuromaton states
(although exponential) is limited and that is why the matching lower bound on
the neuromaton size can be achieved using the standard technique: there exists a
regular language which requires the exponential number of neuromaton states to be
recognized.
Also, a more complex neural transition rule specification makes the emptiness
problem for the neuromata harder than for the classical formalism (finite automata,
regular expressions). On the other hand, while the complement operation in the
nondeterministic case of this formalism can cause an exponential growth of the
descriptional complexity, the complement of the neuromata can be easily achieved.
We have also investigated the Hopfield neuromata which are studied widely due
to their convergence properties. We have shown that Hopfield neuromata determine
the proper subclass of regular languages - the so-called Hopfield languages. Via the
so-called Hopfield condition, we have completely characterized the class of Hopfield
languages.
We can conclude that the neuromata present quite an efficient tool not only for
the recognition of regular languages and of their subclasses respectively, but also
for their description.

Acknowledgement

We are grateful to Markus Holzer, Piotr Indyk, and Petr Savick'y for the stimulating
discussions related to the topics of this paper. Further we thank Tereza Beda-nov'a
who realized the pictures in LaTex environment.



--R

The Design and Analysis of Computer Algorithms.
Efficient Simulation of Finite Automata by Neural Nets.
Learning of Regular Expressions by Pattern Matching.
Complexity Issues in Discrete Hopfield Net- works
Learning and Extracting Finite State Automata with Second-Order Recurrent Neural Networks
Bounds on the Complexity of Recurrent Neural Network Implementations of Finite State Machines.

Optimal Simulation of Automata by Neural Nets.
Personal Communication.
A Note on the Space Complexity of Some Decision Problems for Finite Automata.

Representation of Events in Nerve Nets and Finite Au- tomata

Computational Complexity of Neural Networks: A Survey.
Circuit Complexity and Neural Networks.



Discrete Neural Computation A Theoretical Foundation.

Complexity Issues in Discrete Neurocomputing.
Learning Finite State Machines with Self-Clustering Recurrent Networks
--TR
Efficient simulation of finite automata by neural nets
Neurocomputing
A note on the space complexity of some decision problems for finite automata
Learning and extracting finite state automata with second-order recurrent neural networks
Circuit complexity and neural networks
Learning finite machines with self-clustering recurrent networks
Discrete neural computation
Learning and extracting initial mealy automata with a modular neural network model
Bounds on the complexity of recurrent neural network implementations of finite state machines
The Design and Analysis of Computer Algorithms
Computational complexity of neural networks
Hopfield Languages
Learning of regular expressions by pattern matching
hopfield networks;finite neural networks;regular expressions;descriptional complexity;emptiness problem;string acceptors