Tech Report Available

[Arun Jagota]

*************** DO NOT FORWARD TO OTHER BBOARDS*****************
*************** DO NOT FORWARD TO OTHER BBOARDS*****************

The following technical report is available:

   The Hopfield-style network as a Maximal-Cliques Graph Machine

                         Arun Jagota
		    (jagota at cs.buffalo.edu)
                Department of Computer Science
            State University Of New York At Buffalo
                         TR 90-25

                         ABSTRACT

The Hopfield-style network, a variant of the popular Hopfield neural 
network, has earlier been shown to have fixed points (stable states) 
that correspond 1-1 with the maximal cliques of the underlying graph. 
The network sequentially transforms an initial state (set of vertices) 
to a final state (maximal clique) via certain greedy operations. It has 
also been noted that this network can be used to store simple, undirected 
graphs. In the following paper, we exploit these properties to view the 
Hopfield-style Network as a Maximal Clique Graph Machine. We show that 
certain problems can be reduced to finding Maximal Cliques on graphs in 
such a way that the network computations lead to the desired solutions. 
The theory of NP-Completeness shows us one such problem, SAT, that can 
be reduced to the Clique problem. In this paper, we show how this reduction 
allows us to answer certain questions about a CNF formula, via network 
computations on the corresponding maximal cliques. We also present a 
novel transformation of finite regular languages to Cliques in graphs 
and discuss which (language) questions can be answered and how. Our main
general result is that we have expanded the problem-solving ability of the 
Hopfield-style network without detracting from its simplicity and while 
preserving its feasibility of hardware implementation.
------------------------------------------------------------------------

The report is available in compressed PostScript form by anonymous ftp 
as follows:

unix> ftp cheops.cis.ohio-state.edu  (or, ftp 128.146.8.62)
Name: anonymous
Password: neuron
ftp> cd pub/neuroprose
ftp> binary
ftp> get jagota.tr90-25.ps.Z
ftp> quit
unix> uncompress jagota.tr90-25.ps.Z
unix> lpr jagota.tr90-25.ps  (use flag [if any] your printer needs for 
			      Postscript) 

------------------------------------------------------------------------

Due to cost of surface mail, I request use of 'ftp' facility whenever 
convenient. The report, however, is also available by surface mail. 
I am also willing to transmit the LaTeX sources by e-mail.
Send requests (for one or the other) by e-mail to jagota at cs.buffalo.edu.

Please do not reply with 'r' or 'R' to this message.

Arun Jagota
jagota at cs.buffalo.edu

Dept Of Computer Science
226 Bell Hall,
State University Of New York At Buffalo,
NY - 14260

*************** DO NOT FORWARD TO OTHER BBOARDS*****************
*************** DO NOT FORWARD TO OTHER BBOARDS*****************