Thumbnail
Access Restriction
Subscribed

Author Sima, Ji ♦ Wiedermann, Ji
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1998
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Hopfield networks ♦ Descriptional complexity ♦ Emptiness problem ♦ Finite neural networks ♦ Regular expressions ♦ String acceptors
Abstract 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 $\textit{n}$ is recognized by a neuromaton with $&THgr;(\textit{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;(<?Pub Fmt italic>n<?Pub Fmt /italic>) for a single <?Pub Fmt italic>n<?Pub Fmt /italic>-bit string recognition are described. They both require <?Pub Fmt italic>O(n1/2)<?Pub Fmt /italic> neurons and either <?Pub Fmt italic>O(n)<?Pub Fmt /italic> connections with constant weights or <?Pub Fmt italic>O(n1/2)<?Pub Fmt /italic> edges with weights of the O<fen $lp="par">2^{n}$ 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.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1998-01-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 45
Issue Number 1
Page Count 24
Starting Page 155
Ending Page 178


Open content in new tab

   Open content in new tab
Source: ACM Digital Library