THEORY OF NEUROMAS

A finite automaton-the so-called neuromaton, realized by a finite disc rete recurrent neural network, working in parallel computation mode, i s considered. Both the size of neuromata (i.e., the number of neurons) and their descriptional complexity (i.e., the number of bits in the n euromaton representation) are studied. It is proved that a constant ti me delay of the neuromaton output does not play a role within a polyno mial descriptional complexity. It is shown that any regular language g iven by a regular expression of length n is recognized by a neuromaton with Theta(n) neurons. Further, it is proved that this network size i s, in the worst case, optimal. On the other hand, generally there is n ot an equivalent polynomial length regular expression for a given neur omaton. Then, two specialized constructions of neural accepters of the optimal descriptional complexity Theta(n) for a single n-bit string r ecognition are described. They both require O(n(1/2)) neurons and eith er O(n) connections with constant weights or O(n(1/2)) edges with weig hts of the O(2(root n)) size. Furthermore, the concept of Hopfield lan guages is introduced by means of so-called Hopfield neuromata (i.e., o f neural networks with symmetric weights). It is proved that the class of Hopfield languages is strictly contained in the class of regular l anguages. The necessary and sufficient so-called Hopfield condition st ating when a regular language is a Hopfield language, is formulated. A construction of a Hopfield neuromaton is presented for a regular lang uage satisfying the Hopfield condition. The class of Hopfield language s is shown to be closed under union, intersection, concatenation and c omplement, and it is not closed under iteration. Finally, the problem whether a regular language given by a neuromaton (or by a Hopfield acc eptor) is nonempty, is proved to be PSPACE-complete. As a consequence, the same result for a neuromaton equivalence problem is achieved.