Theory of neuromata. - íma, Jiří
A finite automaton?the 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;(n) for a single n-bit string recognition are described. They both require O(n1/2) neurons and either O(n) connections with constant weights or O(n1/2) edges with weights of the O2n Hopfield condition stating when a regular language is a Hopfield language, is formulated. A construction of a Hopfield neuromaton is presented for a regular language satisfying the Hopfield condition. The class of Hopfield languages is shown to be closed under union, intersection, concatenation and complement, and it is not closed under iteration. Finally, the problem whether a regular language given by a neuromaton (or by a Hopfield acceptor) is nonempty, is proved to be PSPACE-complete. As a consequence, the same result for a neuromaton equivalence problem is achieved.
Keywords: Theory of computation; Computation by abstract devices; Models of computation; Automata (e.g., finite, push-down, resource-bounded).; Relations between models; Self-modifying machines (e.g., neural networks).; Mathematical logic and formal languages; Formal languages; Theory