\documentstyle{article}
\topmargin -1.0in
\textheight 9.5in
\textwidth 6.5in
\hoffset -1.0in
\title{\bf A Hopfield-Style Network and Graph Theory/Algorithms
\footnote{Presented at ``Theoretical Issues in Neural Networks'' Workshop
--- Center for Discrete Mathematics and
Theoretical Computer Science, Rutgers University Campus, May 20-23 1991.
To Appear in a DIMACS TR probably in June 91}}
\author{Arun Jagota \\
(jagota@cs.buffalo.edu) \\ 
Department Of Computer Science,\\ 
State University Of New York at Buffalo, NY 14260 
}
\date{}
\begin{document}
\maketitle
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{defn}{Definition}
\newtheorem{corollary}{Corollary}
\newtheorem{remark}{Remark}
\newtheorem{example}{Example}
\newtheorem{NEG}{Negative Result}
\newtheorem{fact}{Fact}
\begin{abstract}
A variant (essentially a special-case) of the discrete Hopfield Network 
is discussed whose weight matrix off-diagonal elements are 
restricted to $\{\rho,(0,1]\}$, where $\rho < 0$ is a 
network parameter. 
It is shown that for sufficiently negative $\rho$, the network stable
states are
the {\em maximal cliques} of a graph underlying the weight matrix. 
Various network properties that emerge primarily as a consequence
of this property are discussed. These include its information capacity,
stable storage for any collection of binary vectors, 
any relation, and any ``multi-relation'', bounds on stable state size,
some conditions for perfect storage, and NP-completeness of the
global energy minimum. Other properties that arise
primarily due to the restrictions on the weight matrix are
discussed. These include properties of various energy-descent dynamics,
convergence in linear number of cycles, and network stable states
as ``$k$-uniformly-dense'' vertex sets. Steepest Energy-descent
dynamics on this network is related to a greedy large-clique finding algorithm 
(MAX) on graphs.
\end{abstract}
This paper is organised as follows.
\tableofcontents
\section{Model}
\subsection{Architecture : $w_{ij} \in \{\rho,(0,1]\},i \neq j, \rho < 0$}
The basic architecture of the Hopfield-Style network is identical to that
of the discrete Hopfield network.
It is a
fully connected one layer network with $N$ units, the $i^{th}$ unit 
denoted by $p_i$ and the weight (connection) between $p_i, p_j, i \neq j$ 
denoted by $w_{ij}$. 
Weights
are symmetric ($w_{ij}~=~w_{ji}$), and there are no self-weights ($w_{ii}$). 
$p_i$ is also used to denote the state of a unit, $p_i(t)$ denotes its state at time $t$.
Unit states are binary ($p_i(t) \in \{0,1 \}$).
The following energy function is defined for the network, which
differs from the Hopfield energy function in the second term
\begin{equation}
E(\bar{p},t) = -\frac{1}{2} \sum_{i} \sum_{j \neq i} w_{ij}~p_j(t)~p_i(t) -\sum_{i} w_0 p_i(t) \label{eq:model1}
\end{equation}
Here, $w_0$ is a sufficiently small positive constant which 
represents the bias 
for $p_i$ to switch ON in the event that $\sum_{j} w_{ij} p_j~=~0$.
It is used to prevent
$\bar{0}$, that is all units being inactive, from
being a stable state. This is required for theorem 2 (see Section 1.4).
We have shown elsewhere \cite{kn:tr9025} that
choosing $w_0 < \frac{1}{\mbox{Denominator($\rho$)}}$ suffices for
the two-state weights form (see next paragraph). 
\par
The main feature of the Hopfield-Style Network
is that for all distinct $i,j$, $w_{ij} \in \{\rho,(0,1]\}$ where
$\rho < 0$. That is, all positive weights are 
$> 0$ and $\leq 1$, and all negative weights have the
same value $\rho$.  We call this the {\em graded-weights} form.
In this paper, we will also consider a special case of the graded-weights form in which
for all distinct $i,j$ $w_{ij} \in \{\rho,1\}$. We call this
the {\em two-state weights} form.
We consider it not
only for its simplicity but also because of its implications to
low-precision VLSI implementations of the Hopfield-Style
Network.
An important way to characterise the weight matrix of the
Hopfield-Style Network is as follows.
Let $G_N~=~(V,E)$ be the {\em simple undirected} graph underlying the network
defined as follows. $V(G_N)$, the vertex set, is equal to
$\{ p_1, \ldots p_{N}\}$, the set of units. $G_N$ has an edge
$(p_i, p_j),~~i \neq j$ if and only if $w_{ij} > 0$.
All properties in this paper depend
only on $\rho$ and $G_N$, that is, only on $\rho$ and the sign
of the weights. 
\subsection{Energy-Descent Dynamics : Discrete Serial Update}
On the Hopfield-Style Network we allow only {\em serial update} dynamics. 
Our use of
the terms {\em asynchronous} and {\em synchronous} is slightly different,
as shown below.
Given the network state ($\bar{p}(t)$) at time $t$, first, for each
unit $p_i$, the 
quantities $n_i, V_i$ and $\Delta E_i$ are computed simultaneously
(in parallel) as follows. 
\begin{eqnarray}
n_i(t+1) & = & \sum_{j \neq i} {(w_{ij}  p_j(t))} + w_0 \\ \label{eq:model4}
V_i(t+1) & = &
\left\{ 
\begin{array}{rl}
1 & \mbox{if $n_i(t+1) > 0$ and $p_i(t) = 0$} \nonumber \\
-1 & \mbox{if $n_i(t+1) < 0$ and $p_i(t) = 1$} \nonumber \\
0 & \mbox{otherwise}
\end{array} 
\right. \nonumber \\
\Delta E_i(t+1)  &  =  &- V_i(t+1) n_i(t+1) \label{eq:model5} 
\end{eqnarray}
where $n_i(t+1)$ is the net input into $p_i$ at time $t+1$, $V_i$
is the direction $p_i$ is allowed to switch in and $\Delta E_i$
is the change in energy this switch would cause. 
Next, 
a unit $p_s$ is picked according to the following
equation and if $\Delta E_s < 0$ then switched as below.
If $\Delta E_s \geq 0$ then no unit is switched.
\begin{eqnarray}
s & = & F(\bar{\Delta E}) \label{eq:model6} \\
p_s(t+1)  & = &
\left\{ 
\begin{array}{rl}
1 & \mbox{if $V_s(t+1) = ~~1$} \\
0 & \mbox{if $V_s(t+1) = -1$} \\
\end{array} 
\right. 
\end{eqnarray}
where $F$ is a function that takes all the $\Delta E_i$ (for all $p_i$)
as arguments and returns the index of the single unit $p_s$ that is
to be switched, if possible. 
\begin{description}
\item [Generic Asynchronous---] 
$F$ selects $p_s$ randomly, arbitrarily, or in some order. The
selected unit checks its input and switches if possible.
Since the selection does not require that
$\Delta E_s(t+1) < 0$, no global communication is involved,
although global control is still required, for the selection. Compared
with a synchronous dynamics (see below), such 
dynamics might be more feasible to implement in physical analog or optical
devices. The main disadvantage is that in many cycles, no unit will
switch. 
\item [Generic Synchronous---]
$F$ selects $p_s$ so that $\Delta E_s(t+1) < 0$,
if such a condition can be satisfied. If not, then $F$ can select any
$p_s$. The disadvantage is that this requires global communication,
one consequence of which is that analog or optical
implementations could be difficult. The main advantage is that in
every cycle a unit switches, on the Hopfield-Style Network 
guaranteeing rapid convergence, as we shall see.
\begin{description}
\item [Arbitrary---]
$F$ is allowed to select {\em any} (not necessarily random) $p_s$ so that 
$\Delta E_s(t+1) < 0$,
if such a condition can be satisfied. The main advantage is that
$F$ can be computed in constant time,
requiring only finding any one component of the $n$-vector $\bar{\Delta E}$
that has a negative value. 
\item [Steepest---]
$F$ selects the (any if not unique) $p_s$ that 
has the {\em minimum} value of energy $\Delta E_s$.
The main disadvantage is that computing $F$ requires roughly $\log n$
time, requiring finding the position of the minimum value of
the $n$-vector $\bar{\Delta E}$.
The main advantage is that the steepest descent dynamics has attractive
properties on the Hopfield-Style Network (see Section 1.7).
\end{description}
\end{description}
\par 
The true Hopfield asynchronous dynamics allows each unit
to independently check its input and switch if possible, with
some constant probability per unit time. This requires no global
communication, 
nor any global control. All properties that we show to
apply for the Generic Asynchronous dynamics on the Hopfield-Style
Network also apply to this true Hopfield asynchronous dynamics,
modulo the possibility that two units choose to update at the
same moment.
\subsection{Convergence in $\leq 2 N$ (linear) cycles}
For the asynchronous energy-descent
rule, the Hopfield-Style Network always converges. This 
follows as a consequence of the fact that it is a special case of the 
Hopfield Network, the result holding for the latter \cite{kn:Hop82}.
As a consequence, the Network also converges for our generic synchronous
energy-descent rule. 
Additionally, we show the following important result.
\begin{theorem}
For $\rho < -N$, and for a generic synchronous energy-descent rule,
the Hopfield-Style Network converges from any initial state
in $\leq 2N$ cycles. 
\end{theorem}
One importance of this theorem is
that it holds for all instantiations of the generic synchronous
energy-descent rule--- for e.g. 
deterministic (steepest descent or otherwise), or stochastic instantiations. 
The other importance is that the condition on $\rho$ required by
this theorem is sufficient for the information storage results (Section 
2).
A consequence of this theorem is that for the asynchronous energy-descent
rule,  
the number
of unit-switching cycles 
involved in any convergence
is $\leq 2N$.
\subsection{Network Stable States as Maximal Cliques}
The property that 
$w_{ij} \in \{\rho,(0,1]\}$, for $\rho < 0$
has allowed
the establishment of a correspondence between the network stable states and
properties of $G_N$, the graph underlying the network. This
correspondence is captured by theorem 2 below,
which holds for any instance of the generic (synchronous or asynchronous) 
energy-descent rule. 
A network stable state $s$ is a local
minimum of the energy function $E$ in eqn (\ref{eq:model1}), that
is, 
the energy of every neighboring
state of $s$ (Hamming distance of $1$ from $s$) is not less than that of $s$. 
A {\bf clique} is a set of vertices in a graph $G$ that has
an edge
between every pair of vertices in this set.
A clique is {\bf maximal} if no proper 
superset of it is also a clique. 
Let
\[
s_m =
\left\{
\begin{array}{ll}
\mbox{size of the largest clique of $G_N$} &  \mbox{if known} \\
N & \mbox{otherwise}
\end{array}
\right.
\]
\begin{theorem}
{\em (Jagota,\cite{kn:tr9002},here)}
For $\rho < -\mbox{min$(3 s_m,N)$}$, there is a 1-1 correspondence between the network stable states and the maximal
cliques of $G_N$.
\end{theorem}
In other words, a set of units is a network stable state if and only
if $w_{ij} > 0$ for all pairs of units in that set
and this set is maximal for this property. The exact values
of the positive $w_{ij}$ are irrelevant. 
If it is known that $s_m << N$, as will be the case if the graph to
be stored has only small maximal cliques,
then choosing only a small $|\rho|$ suffices. 
This might improve the feasibility of analog or optical implementations
of weights. \par
Fig 1 shows the graph $G_N$ underlying a network whose stable
states, for $\rho < -5$ are, by theorem 2 
\begin{verbatim}
   { a c e }   { a b d }  { a b c }
\end{verbatim}
the maximal cliques in $G_N$. Replacing all the off-diagonal $0$ entries in the
adjacency matrix of $G_N$ by $\rho$ gives us the weight matrix of
the network.
\begin{center}
{\small
\setlength{\unitlength}{0.0125in}
\begin{picture}(182,211)(163,585)
\thicklines
\put(334,641){\circle{22}}
\put(174,640){\circle{22}}
\put(254,710){\circle{22}}
\put(334,780){\circle{22}}
\put(175,780){\circle{22}}
\put(175,770){\line( 0,-1){120}}
\put(185,780){\line( 1, 0){135}}
\put(185,640){\line( 1, 0){135}}
\put(265,705){\line( 6,-5){ 65.410}}
\put(245,705){\line(-1,-1){ 60}}
\put(265,715){\line( 1, 1){ 60}}
\put(185,775){\line( 1,-1){ 57.500}}
\put(230,595){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twlsf Graph}}}
\put(170,595){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twlsf Figure 1.}}}
\put(330,635){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twlsf e}}}
\put(170,635){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twlsf c}}}
\put(330,775){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twlsf d}}}
\put(170,775){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twlsf b}}}
\put(250,705){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twlsf a}}}
\end{picture}
}
\end{center}
\subsection{Information Capacity: $\frac{N(N-1)}{2}$}
Abu-Mostafa and Jacques \cite{kn:AbJ85} define the {\em information
capacity} of a Hopfield Network as the logarithm of the number of {\em distinguishable
networks} of $N$ neurons. 
One
definition
of distinguishability, which we call {\em stable-state-distinguishable}, 
is only that the sets of stable states of two such network instances must 
{\em not} be identical.
A second definition of distinguishability, which we call {\em trajectory-distinguishable} 
is that
on at least one input, the state transition sequences generated
by two such network instances are not identical. 
stable-state-distinguishable $\Longrightarrow$ trajectory-distinguishable.
The latter is more
faithful to the idea that the Hopfield Network is a dynamical system
and its trajectories also carry information. 
For the Hopfield-Style Network, for $\rho < -N$, 
every distinct $G_N$ instance embeds a single distinct collection of 
maximal cliques ($=$ stable states). 
That is, it gives a distinct and unique (exactly one) 
stable-state-distinguishable network instance \footnote{Although
more than one network instance may map to a single stable-state-distinguishable network instance}. Every network instance
has a $G_N$.
Hence the number of distinct stable-state-distinguishable networks is
the number of labelled graphs on $N$ vertices, which is
$2^{\frac{N(N-1)}{2}}$. Hence the information capacity by the
stable-state-distinguishable definition is $\frac{N(N-1)}{2}$, that is, exactly one
bit of information per connection. \par
Information Capacity is one measure for comparing different 
associative memory network models.
By comparison, the Information Capacity of the Hopfield Network, 
allowing the weight matrix to be constructed in {\em any} way, 
is $N^3$ \cite{kn:AbJ85}. With an identity weight matrix, a bi-polar
Hopfield Network provides stability to any collection of vectors.
But its Information Capacity is $0$. \par
{\bf Some Open Questions :}
Information Capacity for the trajectory-distinguishable definition.
Information Capacity for arbitrary $\rho < 0$ (see Section 1.8).
\subsection{Generic Energy-descent: clique $\rightarrow$ maximal clique completion}
The following property has applications to
pattern completion and certain kinds of
Combinatorial Problem Solving. 
It
holds for any (synchronous or asynchronous) energy-descent rule. 
Corollary 1 provides an improved convergence bound, when the condition of theorem 3 holds.
Let $S_a(t)$ 
denote the set of units active (ON) at time $t$. 
$S_a(0)$ is the set of 
units ON in the input (network initial state). 
\begin{theorem}
When $\rho \leq -s_m$, if $S_a(0)$, the initial network state (input)
is a clique, then
$S_a(f)$, the stable state reached by the network is a 
superset of $S_a(0)$ and a maximal clique.
\end{theorem}
\begin{corollary}
When $\rho \leq -s_m$, if $S_a(0)$
is a clique, then the number of cycles in which the network 
converges is less than or equal to $s_m - |S_a(0)|$.
\end{corollary}
\subsection{Steepest Energy-Descent: $\rightarrow$ Greedy Clique-Finding Algorithm}
The Steepest Energy-Descent
rule applied to the Hopfield-Style Network has the following
properties.
\begin{theorem}
{\em (Jagota, \cite{kn:tr9002}) }
With $\rho < -2 N$,
let the input, $S_a(t_0)$, be presented to the network at time $t_0$. 
The network has the following dynamics in the following order.
\begin{enumerate}
\item The network switches OFF units 
successively (one by one) in the first $k \geq 0$ steps until the first time
$S_a(t_{k})$ becomes a clique of $G_n$. At that time, $|S_a(t_{k})| = |S_a(t_0)| - k$. 
\item The network, then switches ON units successively (one by one) in the next 
$j \geq 0$ steps until $S_a(t_{k+j})$ is a maximal clique of $G_n$. At that time,
$|S_a(t_{k+j})| = |S_a(t_{k})| + j$.
\end{enumerate}
$S_a(t_{k+j})$ is the stable state of the network. 
\end{theorem}
\begin{lemma}
{\em (Jagota, \cite{kn:tr9002}) }
With $\rho < -2 N$,
If $S_a(t_i)$ is not a clique, then at time $t_{i+1}$, the unit 
inhibited by the largest number of units in $S_a(t_i)$
will be switched OFF.
\end{lemma}
\subsubsection*{Greedy Algorithm}
There is a direct correspondence between the steepest descent properties
described above and {\em greedy} clique finding operations on graphs.
In particular, the two-state weights form network emulates the following
greedy algorithm on $G_N$. 
Let the initial state of the network be $S_a(t_0)$.
\begin{enumerate}
\item $G_i \leftarrow G_N[S_a(t_0)]$;
\item \underline{while} $V(G_i)$ is not a clique \underline{do}
\begin{enumerate}
\item Pick {\bf a} $v \in V(G_i)$ with minimum degree, that is: $d_{G_{i}}(v) = \delta(G_i)$;
\item $G_i \leftarrow G_i~-~\{v\}$;
\end{enumerate}
\item \underline{end};
\item \underline{while} $\exists x \in V(G_N)~-~V(G_i)$ such that $V(G_i) \cup \{x\}$ is a clique \underline{do}
\begin{enumerate}
\item Pick {\bf a} $y \in V(G_N)~-~V(G_i)$ such that $V(G_i) \cup \{y\}$ is a clique;
\item $G_i \leftarrow G_i \cup \{y\}$;
\end{enumerate}
\item \underline{end};
\end{enumerate}
The above algorithm does all the switch OFF's before any switch ON's.
This is consistent with theorem 3.
Step 2a of the algorithm switches a unit OFF that is inhibited by the 
{\em largest} number of active units, which is consistent with lemma 2.
Step 4a switches a unit ON if it is currently inactive and receives 
excitation from {\em all} the active units, which is consistent with
theorem 3.
If there are multiple vertices that satisfy the criteria to
pick $v$ in Steps 2a and 4a, the choice is
random. 
This is consistent with our steepest 
energy-descent rule which also makes
a random choice from the same set of candidate units, units
with the same minimum energy $\Delta E_i$. \par
With the initial state $S_a(0) \leftarrow V(G_N)$, 
the above algorithm that the network emulates becomes the greedy 
algorithm to find a large maximal clique.
It is well known in the field of graph theory and algorithms that after the
greedy algorithm terminates, a lower bound 
on the size of the clique is, 
\begin{equation}
 \sum_{v \in V} \frac{1}{|V|~-~d(v)} \label{eq:greedylb}
\end{equation}
One way to see this is that the greedy clique algorithm on $G_N$
is equivalent to the greedy Independent Set (IS) algorithm called MAX
on $G_N^{c}$. 
Griggs \cite{kn:Gri83} gives
the lower bound of IS obtained by MAX, from which equation (\ref{eq:greedylb})
is obtained by replacing the degrees by the co-degrees.
\subsection{Network Stable States as ``$k$-uniformly-dense'' vertex sets}
The network stable states can be described as $k$-uniformly-dense
vertex sets (cliques are a special case with $k=\infty$).
\begin{defn}
Let $G~=~(V,E)$ be a graph and $G'=G[V']; V' \subseteq V$
be the $V'$-induced subgraph of $G$. We say that $V'$ is a 
$k$-uniformly-dense vertex set,$ 0 \leq k \leq \infty$
{\em iff}
\[ \forall v \in V',~~~~\frac{d_{G'}(v)}{\bar{d}_{G'}(v)} \geq k \]
\end{defn}
We use uniform-density$(V')$ to denote the maximum $k$ for which
V' is a $k$-uniformly-dense vertex set. 
For the two-state weights form, the energy-descent rule equation 
(~\ref{eq:model4}) can be written
in the following form, which will be quite convenient for the proofs
that follow. 
For any unit $p_y$,
\begin{equation}
n_y(t_{i~+~1})~=~\rho~\bar{d}(y)|S_a(t_i)~~+~~d(y)|S_a(t_i)~+~w_0 \label{eq:clu4}
\end{equation} 
For the {\em graded-weights} network form, the same energy-descent rule
equation (~\ref{eq:ni}) for $p_y$ can be written as
\begin{equation}
n_y(t_{i+1})~=~\rho~\bar{d}(y)|S_a(t_i)~~+~\sum_{x \in d(y)|S_a(t_i)} {w_{xy}} \label{eq:cll1} 
\end{equation}
where $w_{xy} \in (0,1]$. \par
We will present positive results (that a property holds) and negative results
(that a property does not hold). If a positive result holds for the
{\em graded-weights} form, it also holds for the special case {\em two-state} weights
form. If a negative
result holds for the {\em two-state} weights form, it also holds for
the general case {\em graded-weights} form. 
The first series of results describe network stable states in terms of
$k$-uniformly-dense vertex sets and explain why the analog of theorem 2
does not hold. They hold for any energy-descent rule.
\begin{lemma}
(Jagota,\cite{kn:tr9002})
In the graded-weights form, a necessary condition for $S$ to be a network stable state is that
\begin{equation}
\mbox{uniform-density}(S)~~\geq~~-\rho \label{eq:clu1}
\end{equation}
\end{lemma}
Theorem 2 requires that
a network stable state satisfy the property of being a clique {\em maximally}. 
Lemma 2 does not require that, to be a network stable state, the vertex
set satisfy the condition of Lemma 2 maximally. The following negative
result explains why. 
\begin{NEG}
In the two-state weights form, there can be vertex sets 
satisfying the condition of Lemma 2 non-maximally but still be
network stable states. 
\end{NEG}
{\bf Example :}
Let the graph in Fig 1b be $G_N$, the graph underlying the network, 
and let $\rho~=~-2.2$.
From Fig 1b and Eqn (~\ref{eq:clu4}), if 
$S_a(t_i)~=~\{ a,b,e \}$, then $n_c(t_{i+1}),n_d(t_{i+1}),n_f(t_{i+1}) < 0$.
So none of these units can switch ON. From Fig 1b
uniform-density$(\{a,b,e\}) = \infty \geq -\rho$ and hence by Lemma 3
(next result), no unit in $S_a(t_i)$
will switch OFF.
Hence \{a,b,e\} is a network stable state. 
From Fig 1b,
uniform-density$(\{a,b,e,f,c\}) = 3 \geq -\rho$ 
so that \{a,b,e\} satisfies the condition of Lemma 2 but not maximally.
\par
Theorem 2 provides a sufficient condition (maximal clique) for a
vertex set $S$ to be a network stable state. 
This sufficient condition cannot be generalised
to a condition in
terms of the uniform-density of $S$, for arbitrary $\rho$. The following
negative result explains why.
\begin{NEG}
In the two-state weights form, there can be vertex
sets $S$ that maximally satisfy the condition 
uniform-density$(S) \geq -\rho$ but are still not network stable states.
\end{NEG}
{\bf Example :}
Let the graph in Fig 1c be $G_N$, the graph underlying the network, 
and let $\rho~=~-1$.
We note that
uniform-density$(\{a,b,c\}) = 1 \geq -\rho$.
Moreover, uniform-density$(\{a,b,c,d\}) = \frac{1}{2} < -\rho$,
so \{a,b,c\} is maximal for this property.
From Fig 1c $\frac{d(d)|\{a,b,c\}}{\bar{d}(d)|\{a,b,c\}} = 2 \geq -\rho$
and by Eqn (~\ref{eq:clu4}), if 
$S_a(t_i)~=~\{ a,b,c \}$, then $n_d(t_{i+1}) > 0$ which means
d will switch ON at $t_{i+1}$ (see also Lemma 4).
Hence \{a,b,c\} is not a network stable state. 
\par
The next major result of this section is that the greedy algorithm that describes
the network steepest energy-descent dynamics when the network stable states are maximal cliques
is incapable, after references to cliques in the algorithm are replaced
by $k$-uniformly-dense sets, of describing the dynamics when such states 
are $k$-uniformly-dense vertex sets, for arbitrary $k$, that is, 
for arbitrary $\rho < 0$. Specifically, we show that certain properties
of theorem 4 and lemma 1, which hold when the stable states are maximal
cliques, do not hold when they are $k$-uniformly-dense vertex sets, for
arbitrary $k$.
The remarks that follow the positive results show that they
do not hold for the graded-weights form, that is, the restriction to
{\em two-state weights} form gives the network these additional properties.
\begin{lemma}
In the two-state weights form, for any energy-descent rule,
uniform-density$(S_a(t_i)) \geq -\rho$ $\Rightarrow$ no unit switches OFF at
$t_{i+1}$.
\end{lemma}
{\bf Proof:}
Suppose uniform-density$(S_a(t_i)) \geq -\rho$. 
By definition of uniform-density,
\[ \forall x \in S_a(t_i)~~~~~~ \frac{d(x)|S_a(t_i)}{\bar{d}(x)|S_a(t_i)} \geq -\rho \]
From this and Eqn (~\ref{eq:clu4}),
\[ \forall x \in S_a(t_i) ~~~~~~n_x(t_{i+1}) > 0 \]
It follows that no unit can switch OFF at $t_{i+1}$. 
$\Box$ \newline
{\bf Remark: }
Lemma 3 does not hold in the {\em graded-weights} form because, in general, 
it is possible to
choose $w_{xy} \in (0,1]$ sufficiently small so that
even when uniform-density$(S_a(t_i)) \geq -\rho$
, by Eqn (~\ref{eq:cll1})
\[ \exists x \in S_a(t_i)~\mbox{such that}~n_x(t_{i+1}) < 0 \]
It is possible that this $x$ can switch $\Box$.
\par
By theorem 4, when $\rho < -2 N$, if $S_a(t_i)$ is not a clique,
then for the steepest energy-descent rule, a unit must switch OFF at time $t_{i+1}$. The following
negative result explains why this need not occur for
arbitrary $\rho < 0$. For a generic energy-descent rule, this result
clearly holds.
\begin{NEG}
In the two-state weights form, even for the steepest
energy-descent rule, uniform-density$(S_a(t_i)) < -\rho$ does not 
imply that a unit switches OFF at $t_{i+1}$.
\end{NEG}
{\bf Example :}
Let the graph in Fig 1d be $G_N$, the graph underlying the network, 
and let $\rho~=~-2$.
We note that
uniform-density$(\{a,b,c\}) = 1 < -\rho$.
But from Fig 1d and Eqn (~\ref{eq:clu4}), if 
$S_a(t_i)~=~\{ a,b,c \}$, then 
\[ n_a(t_{i+1})~=~-1,~n_c(t_{i+1})~=~-1,n_b(t_{i+1})~=~2,~n_d(t_{i+1})~=~3 \].
Hence d will switch ON at $t_{i+1}$ $\Box$.
\par
Also by
theorem 4, when $\rho < -2 N$, for the steepest energy-descent rule,
if $S_a(t_i)$ is a non-maximal clique, 
then at time $t_{i+1}$,
\begin{enumerate}
\item A unit switches ON. 
\item $S_a(t_{i+1})$ is also a clique.
\end{enumerate}
1). generalises to arbitrary $\rho < 0$, 
as shown by Lemma 4 below. It requires a different condition,
however. In particular, the condition of Lemma 4 cannot be
replaced by ``$S_a(t_i)$ is a non-maximal $-\rho$-uniformly-dense
vertex set'' (see Negative Result 2).
2). does not generalise however, as shown by Negative Result 4.
\begin{lemma}
In the two-state weights form, for any
energy-descent rule, if uniform-density$(S_a(t_i)) \geq -\rho$ 
and
$ \exists x \in V(G_N)~-~S_a(t_i)$ 
such that $\frac{d(x)|S_a(t_i)}{\bar{d}(x)|S_a(t_i)} \geq -\rho$
then
at time $t_{i+1}$, 
some unit $y \in V(G_N)~-~S_a(t_i)$ 
such that $\frac{d(y)|S_a(t_i)}{\bar{d}(y)|S_a(t_i)} \geq -\rho$
will switch ON.
\end{lemma}
{\bf Proof:}
Since uniform-density$(S_a(t_i)) \geq -\rho$, By Lemma 3, no
unit in $S_a(t_i)$ can switch OFF.
Substituting the particular unit $x$ that satisfies the condition
of Lemma 4 into Eqn (~\ref{eq:clu4}), $n_x(t_{i+1}) > 0$. 
Hence, if no other unit switches ON, $p_x$ will switch
ON, at time $t_{i+1}$. Suppose some other unit $p_y$ switches ON.
This means $n_y(t_{i+1}) > 0$. 
Noting that $w_0$ is sufficiently small not to interfere,  by
Eqn (~\ref{eq:clu4})
\[ \frac{d(y)|S_a(t_i)}{\bar{d}(y)|S_a(t_i)} \geq -\rho \]
$\Box$ \newline
{\bf Remark:}
Lemma 4 does not hold in the {\em graded-weights} form.
It is possible to
choose, for every $p_y \in V(G_N)-S_a(t_i)$ satisfying
$\frac{d(y)|S_a(t_i)}{\bar{d}(y)|S_a(t_i)} \geq -\rho$, 
the positive weights $w_{xy} \in (0,1]$, from all $p_x \in S_a(t_i)$, 
sufficiently small, so that according to Eqn (~\ref{eq:cll1}),
$n_y(t_{i+1}) < 0 $,
which would mean that no such $p_y$ could switch ON at $t_{i+1}$. \par
\begin{NEG}
In the two-state weights form, for any energy-descent rule,
if uniform-density$(S_a(t_i)) \geq -\rho$ 
and
at time $t_{i+1}$
some unit 
switches ON, then it does not imply that 
uniform-density$(S_a(t_{i+1})) \geq -\rho$.
\end{NEG}
{\bf Example :}
Again, let the graph in Fig 1c be $G_N$, the graph underlying the network, 
and let $\rho~=~-1$.
With
$S_a(t_i)~=~\{ a,b,c \}$,
uniform-density$(S_a(t_i)) = 1 \geq -\rho$
and 
$\frac{d(d)|S_a(t_i)}{\bar{d}(d)|S_a(t_i)} = 2 \geq -\rho$
so that $n_d(t_{i+1}) > 0$. d switches ON at $t_{i+1}$ and so
$S_a(t_{i+1})~=~\{ a,b,c,d \}$
But 
uniform-density$(S_a(t_{i+1})) = \frac{1}{2} < -\rho$.
\begin{center}
\setlength{\unitlength}{0.0125in}
\begin{picture}(389,335)(54,423)
\thicklines
\put(431,743){\circle{20}}
\put(432,670){\circle{20}}
\put(354,671){\circle{20}}
\put(352,743){\circle{20}}
\put(353,571){\circle{20}}
\put(355,499){\circle{20}}
\put(433,498){\circle{20}}
\put(432,571){\circle{20}}
\put(254,619){\circle{20}}
\put(234,673){\circle{20}}
\put(197,581){\circle{20}}
\put(108,582){\circle{20}}
\put(152,638){\circle{20}}
\put( 64,638){\circle{20}}
\put( 74,433){\line( 1, 0){355}}
\put(364,670){\line( 1, 0){ 57}}
\put(360,736){\line( 6,-5){ 66.393}}
\put(352,732){\line( 0,-1){ 50}}
\put(362,742){\line( 1, 0){ 58}}
\put(426,563){\line(-1,-1){ 62}}
\put(365,499){\line( 1, 0){ 58}}
\put(433,561){\line( 0,-1){ 53}}
\put(363,569){\line( 1, 0){ 59}}
\put(354,560){\line( 0,-1){ 50}}
\put(250,609){\line(-5,-6){ 54.590}}
\put(115,575){\line( 5,-2){ 81.724}}
\put( 73,643){\line( 5, 1){150}}
\put(160,643){\line( 5, 2){ 63.793}}
\put(238,663){\line( 1,-3){ 11.100}}
\put(230,663){\line(-2,-5){ 28.759}}
\put(205,587){\line( 3, 2){ 39}}
\put(162,635){\line( 6,-1){ 82.865}}
\put(158,630){\line( 4,-5){ 32}}
\put(114,590){\line( 5, 6){ 32.295}}
\put( 74,637){\line( 1, 0){ 68}}
\put( 70,629){\line( 5,-6){ 31.311}}
\put(380,471){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twltt (d)}}}
\put(381,607){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twltt (c)}}}
\put( 80,435){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twltt Fig 1 b,c,d - Examples for negative results}}}
\put(428,491){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twltt c}}}
\put(351,493){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twltt d}}}
\put(429,562){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twltt b}}}
\put(349,564){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twltt a}}}
\put(427,664){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twltt c}}}
\put(350,665){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twltt d}}}
\put(427,737){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twltt b}}}
\put(349,737){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twltt a}}}
\put( 60,631){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twltt a}}}
\put(148,632){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twltt b}}}
\put(104,576){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twltt c}}}
\put(193,574){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twltt d}}}
\put(229,666){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twltt e}}}
\put(251,612){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twltt f}}}
\put(166,514){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twltt (b)}}}
\end{picture}
\end{center}
By Lemma 1, for the steepest energy-descent rule with $\rho < -2 N$, if $S_a(t_i)$ is not a clique,
then at time $t_{i+1}$, a unit (in $S_a(t_i)$) inhibited by the largest
number of active units will be switched OFF.
This {\em is} the switch OFF
property responsible for the network's greedy behavior and 
exploited to emulate the clique finding greedy algorithm.
Unfortunately, by Negative Result 3, we have already seen that
it does not generalise to arbitrary $\rho$, since
uniform-density$(S_a(t_i)) < -\rho$ does not guarantee that
a unit will even switch OFF at time $t_{i+1}$. Lemma 3 
says however, that if a unit does switch OFF, then
uniform-density$(S_a(t_i) < -\rho$. The following Lemma adds more to
this statement.
\begin{lemma}
In the two-state weights form, for the steepest energy-descent rule,
if a unit switches OFF at time $t_{i+1}$, then it 
is inhibited by the largest number of units in $S_a(t_i)$.
\end{lemma}
{\bf Proof:} \newline
Let $p_l \in S_a(t_i)$ such that $d(p_j)|S_a(t_i)~=~\delta(G_N[S_a(t_i)])$.
That is, $p_l$ is an active unit inhibited by the largest number of active
units.
Suppose $p_s$ is inhibited by fewer active units than $p_l$,
that is, $\bar{d}(p_s)|S_a(t_i)~<~\bar{d}(p_l)|S_a(t_i)$.
This means
\[ d(p_s)|S_a(t_i)~>~ d(p_l)|S_a(t_i) \]
Also, since $\rho < 0$, 
\[ \rho~\bar{d}(p_l)|S_a(t_i)~<~ \rho~\bar{d}(p_s)|S_a(t_i) \]
From Eqn (~\ref{eq:clu4}), $n_l(t_{i+1}) < n_s(t_{i+1})$ and since
$n_s(t_{i+1}) < 0$, $p_l$ will switch OFF at $t_{i+1}$, which contradicts
assumption.
Hence $p_s$ must be inhibited by at least the same number of units as $p_l$ is by $\Box$.
\newline
{\bf Remark:}
Lemma 5 does not hold for the {\em graded-weights} form.
It is possible to choose the positive
weights from other units in $S_a(t_i)$ to $p_l$ relatively small 
while choosing 
positive weights from other units in $S_a(t_i)$ to $p_s$ relatively large, 
so that even though $p_l$ is inhibited by more units in $S_a(t_i)$ than
$p_s$, $p_s$ receives more inhibition, that is $n_s(t_{i+1}) < n_l(t_{i+1})$.
\par

\subsection{Storage Rule : Stores set by constructing maximal clique}
We 
present a storage rule that constructs a two-state weights form
network.
The initial storage state of the network is
\begin{eqnarray}
w_{ij}(0) & = & \rho~~~\forall i,j~~i \neq j \nonumber 
\end{eqnarray}
where $\rho < 0$.
\subsubsection*{Storage Rule}
Given any set of vertices $S \subseteq V$, $S$ can be stored in the network at time $t$ as follows. For all $i \neq j$,
\begin{equation}
w_{ij}(t+1)~:=~
\left\{
\begin{array}{rl}
1 & \mbox{if $p_i,~p_j~\in S$} \\
w_{ij}(t) & \mbox{otherwise}
\end{array}
\right.
\end{equation}
Any sequence of stores maintains the invariant that
for all $i$ and $j$, $i \neq j$,
$w_{ij} \in \{\rho,1\}$.
\subsubsection*{Graph-theoretic interpretation}
With the network stable states as maximal cliques, the 
operation of the storage rule can be interpreted as follows. Each memory
to be stored is a set, interpreted as a
complete graph. Storing all memories is equivalent to
constructing a graph that is the union of these complete graphs. The
maximal cliques of the resulting graph are the
network stable states. See Figure 3.
\subsection{Global Energy Minimum is NP-Complete}
This result is for the two-state weights form.
Any $N$-vertex graph $G$ can be stored in an $N$-unit network by 
identifying vertices with units, and presenting the edges of $G$ as
binary sets to the storage rule. $G_N$ becomes identical to $G$.
For $\rho < -N$, there is a 1-1 correspondence between the maximal
cliques of $G$ and network stable states. In particular, for
the two-state weights form, from equation (\ref{eq:model1}),
the energy of a clique $S$ is
\[ E(S) = \frac{-|S|(|S|-1)}{2}~-~w_0 |S| \]
that is, (almost) related to the number of edges in $S$.
The larger the clique the lower the energy. $S$ is a maximum clique of $G$ 
is equivalent to $E(S)$ is a global energy minimum of the network.
Since the MAXIMUM CLIQUE
problem is NP-Complete and our above {\em reduction} is in polynomial-time,
the problem of finding a global energy minimum of a Hopfield-Style
Network is NP-Complete.
\section{Information Storage}
\subsection{Stable Storage : Perfect for binary vectors, relations, multi-relations}
\begin{defn}
A network is said to have stored a collection of
memories $C$ {\bf stably}, if for every
stored memory in $C$ there is a unique and distinct {\em network stable state}.
\end{defn}
In other words, 
the network, after storage, remembers every stored memory perfectly.
The {\em stable storage} capacity of the Hopfield network, on
vectors $v \in \{0,1\}^N$ to be stored that are generated randomly and
independently,
is $\approx 0.15 N$. We have done independent experiments, for
$N$ varying from $4$ to $40$, that are
consistent with this number. \par
For the following set of theorems, we assume that $\rho < - min(3 s_m,N)$.
\begin{theorem}
Any n-ary relation $R \subseteq D_1 \times D_2 \ldots \times D_n$
(memories are the n-tuples of $R$) can be stored {\em stably}
in a $|D_1|+|D_2|+ \ldots |D_n|$ unit Hopfield-Style network. 
Here the set of units is $D~=~D_1 \cup D_2 \ldots \cup D_n$.
\end{theorem}
{\bf Example :}
The following example shows how a 3-ary relation $R$ is stored.
\begin{verbatim}
  D1 = {a,b,c},   D2 = {1,2,3},   D3 = {A,B,C}   R  = {(a,1,A), (a,2,B), (c,3,C)}               
\end{verbatim}
$G_N$ after storage is shown in Figure 3.1.
Storing binary vectors is just a special case of storing relations.
\begin{corollary}
Any collection of $n$-dimensional binary vectors can be stored {\em stably}
in a $2n$ unit Hopfield-Style network.
\end{corollary}
{\bf Example :}
The following example shows how three 3-d binary vectors are stored.
\begin{verbatim}
Vectors                    101            011            110
Set Representation    {1-1,0-2,1-3}  {0-1,1-2,1-3}  {1-1,1-2,0-3}
\end{verbatim}
$G_N$ after storage is shown in Figure 3.2.
This example also illustrates a distinctive feature of our
representation. In our network, the values
$0$ and $1$ of a vector component are represented by two units,
whereas in most networks (including the binary Hopfield network),
they are represented in a single unit.
We now generalise our memories from being $n$-tuples
of a relation $R$ to being what we call $\leq$n-tuples of an $n$-ary 
multi-relation $MR$ defined as follows.
\begin{defn}
Let $A_i = D_1 \times D_2 \ldots \times D_i$ and $A = \cup_{i=1,n} A_i$.
Then $MR \subseteq A$ is called an $n$-ary {\em multi-relation} on 
$D_1 \times D_2 \ldots \times D_n$. 
\end{defn}
\begin{theorem}
Any n-ary multi-relation $MR$ on $D_1 \times D_2 \ldots \times D_n$
(memories are the $\leq$n-tuples of $MR$) can be stored {\em stably}
in a $|D_1|+|D_2|+ \ldots +|D_n| + n$ unit HSN network with $n$
size units.
Here the set of units is $D~=~D_1 \cup D_2 \ldots \cup D_n \cup \{1,\ldots,n\}$ 
where the last term represents the $n$ size units, units that encode
the length of a $\leq$n-tuple.
\end{theorem}
{\bf Example :}
The following example illustrates both the representation of
strings as multi-relations and how they are stored in the network.
Store the following words in the network with $k$, the number of
size units, equal to $3$.
\begin{verbatim}
Words              :  a     do       car        dot
Multi-Relation Rep : {a1} {d1,o2} {c1,a2,r3} {d1,o2,t3}
D      = {a1,c1,d1} U {a2,o2 } U { r3,t3 } U { 1,2,3 }
\end{verbatim}
$G_N$ after storage is shown in Figure 3.3.
\begin{remark}
Every collection of $n$-dimensional binary vectors is an
$n$-ary relation, even in the way the network stores them. 
Every result that we state to hold for $n$-ary relations also
holds for collections of $n$-dimensional vectors, with nothing more
to be said.
\end{remark}
\begin{remark}
Every $n$-ary relation 
is also a multi-relation. So theorem 5 directly
provides the stable storage results for relations. 
However, in theorem 5, $n$ size units are required,
even if only relations are to be stored. 
That is why we have Theorem 4, which shows stable storage for
relations, 
without requiring size units. 
Every result that we state to hold
for multi-relations also holds
for relations, but with size units used. 
However, when the same results hold for relations, even without using size
units, we will state them explicitly as theorems.
\end{remark}
\begin{remark}
In the above results
(theorems 5,6, corollary 2), we emphasise that {\bf any}, 
over the other fact that {\bf exponentially} many, memories of the above
types can be stored stably. 
\end{remark}
\subsection{Spurious Memories}
{\em Spurious} memories are new memories, not
among the stored ones, that
form after a collection of memories is stored in a network.
Even though the Hopfield-Style network guarantees stable storage
of binary vectors, relations and multi-relations, spurious memories
can develop for all three. \newline
{\bf Example: } 
Store the following 3-bit binary vectors: $\mbox{111, 100, 001}$.
It can be checked that after storage, the vector $\mbox{101}$ becomes a 
spurious memory. \par
{\bf Some Open Questions :} Characterise how spurious memories develop.
Statistical estimation of how many spurious memories develop on
random memory sets, as a function of their size.
\subsection{Bounding stable state size ($s_m$)}
Even though spurious memories may develop, for multi-relations
and relations it is possible to bound $s_m$,
the size of the largest stable state in the network. This result
allows calculation of $s_m$ solely from the size of the largest
memory to be stored.
We have seen earlier that it
is an important parameter, especially if
it can be bounded to be $ << N$. Because then setting
$\rho < -3(s_m-1)$ would suffice for all our storage results.
\begin{lemma}
For any n-ary multi-relation stored in the network, the size of every network
stable state is $\leq n+1$.
\end{lemma}
\begin{lemma}
For any n-ary relation stored in the network {\bf with $k=0$}, the size of 
every network stable state is $\leq n$.
\end{lemma}
\subsection{Perfect Storage (No spurious) for relations and multi-relations on $D_1 \times D_2$}
We say that the network has {\em perfect} storage for a given
set of memories $C$, if it has 
stable storage for $C$, and if no spurious memories develop after storing
$C$.
The
following lemmas show some conditions under which perfect storage is
guaranteed. 
\begin{lemma}
Perfect storage is guaranteed for binary multi-relations (on $D_1 \times D_2$). 
\end{lemma}
\begin{lemma}
Perfect storage is guaranteed for storing binary relations
$R \subseteq D_1 X D_2$.
\end{lemma}
Perfect storage is also guaranteed for {\em complete} relations and multi-relations. \newline
{\bf Open Questions :} Other non trivial collections of memories for
which perfect storage is guaranteed.
\begin{thebibliography}{160}
\bibitem [AbJ85] {kn:AbJ85} Y.S. Abu-Mostafa and J. St. Jacques,
Information Capacity of the Hopfield Model.
{\em IEEE Trans. Inform. Theory vol. IT-31, no. 4, pp. 461-64, 1985}.
\bibitem [Ama89] {kn:Ama89} Amari, Shun-Ichi (1989). 
Characteristics of Sparsely Encoded Associative Memory.
{\em Neural Networks, Vol 2, No. 6, 1989}.
\bibitem [BoM76] {kn:BM} J.A. Bondy, U.S.R Murty 
Graph Theory with Applications,
{\em North-Holland, 1976}.
\bibitem [GaJ79] {kn:GJ} Garey Michael R., Johnson David S, 
Computers and Intractability - A guide to the theory of NP-completeness (1979).
\bibitem[Gri83] {kn:Gri83}
J. R. Griggs, 
Lower Bounds on the Independence Number in Terms of the degrees. 
{\em Journal of Combinatorial Theory, Series B 34, 22-39, 1983}.
\bibitem [Hop82] {kn:Hop82} Hopfield, J.J. (1982). 
Neural networks and physical systems with emergent computational
properties.
{\em Proceedings of the National Academy of Sciences, USA, 79, 2554-2558}.
\bibitem [Hop84] {kn:Hopfield2} Hopfield, J.J.
Neurons with graded response have collective computational properties
like those of two-state neurons
{\em Proceedings of the National Academy of Sciences, USA, 81, 3088-3092,1984}.
\bibitem [HoT85] {kn:HoT85} J.J. Hopfield and D.W. Tank, 
`Neural' computation of decisions in optimization problems. 
{\em Biological Cybernetics, vol. 52, pp. 141-152, 1985}.
\bibitem [Jag90a] {kn:lexicon} Arun Jagota and Y.T. Hung (1990). 
A neural lexicon in a Hopfield-style network,
{\em Proceedings of the International Joint Conference on Neural
Networks, Wash DC, January 1990}.
\bibitem [Jag90b] {kn:restore} Arun Jagota (1990). 
Applying a Hopfield-style Network to Degraded Printed Text Restoration
{\em Proceedings of the 3rd Conference on Neural
Networks and PDP, Indiana-Purdue University, April 1990}.
\bibitem [Jag90c] {kn:tr9002} Arun Jagota (1990). 
A new Hopfield-style network for content-addressable memories. \newline
{\em TR 90-02, Dept Of Computer Science,
State University Of New York At Buffalo, NY 14260 }
\bibitem [Jag90d] {kn:wordrec} Arun Jagota (1990). 
Applying a Hopfield-style Network to Degraded Text Recognition
{\em Proceedings of the International Joint Conference on Neural
Networks, San Diego, June 1990}.
\bibitem [Jag90e] {kn:tr9025} Arun Jagota (1990). 
The Hopfield-style Network as a Maximal Clique Graph Machine.
{\em TR 90-25, Dept Of Computer Science,
State University Of New York At Buffalo, NY 14260 }
\bibitem [Jag91b] {kn:Jag91a} Arun Jagota (1991). 
Novelty Detection on a very large number of memories stored in a Hopfield-Style network.
{\em To be presented at - IJCNN-91-Seattle, July 1991}
\bibitem[MPRV87] {kn:MPRV87}
R. J. McEliece, E. C. Posner, E. R. Rodemich, and S. S. Venkatesh.
The Capacity of the Hopfield Associative Memory.
{\em IEEE Transactions on Information Theory, Vol. IT-33, No. 4, July 1987}.
\bibitem [TaH85] {kn:TaH85} D.W. Tank and J.J. Hopfield, 
Simple optimization networks: An A/D converter and a linear
programming circuit,
{\em IEEE Trans. Circuits Syst., vol. CAS-33, pp. 533-541, 1986}.
\end{thebibliography}
{\small
\centerline{\bf APPENDIX}
\newcommand{\Suk}{\mbox{$S_{+k}~$}}
\newcommand{\Sajuk}{\mbox{$S_a(j)_{+k}$}}
\newcommand{\Smk}{\mbox{$S_{-k}~$}}
{\bf Preliminaries}
We assume familiarity with the standard terminology of graph
theory.
$\Suk=S \cup \{p_k\}$.
$\Smk=S ~\backslash~ \{p_k\}$ where it is assumed that
$p_k \in S$.
$d(x)|S_a(i)$ is the number of vertices in $S_a(i)$ that $x$
is adjacent to. 
$\bar{d}_G(v)=|V|-1-d_G(v)$ denotes the co-degree
of $v$ in $G$.
$E(S)$ is the energy at state $S \subseteq V(G_N)$.
\begin{eqnarray}
E(S)         & = & - \sum_{i \in S} w_0 
-\frac{1}{2} \sum_{i \in S} \sum_{j \in S-\{i\}} w_{ij} \nonumber \\
E(S)-E(\Suk) & = & w_0 + \sum_{i \in S} w_{ik} \label{eq:appendix1} \\
E(\Smk)-E(S) & = & w_0 + \sum_{i \in \Smk} w_{ik} \label{eq:appendix2}
\end{eqnarray}
\newcommand{\ESmkMS}{\mbox{$E(\Smk)-E(S)~$}}
\newcommand{\ESMSuk}{\mbox{$E(S)-E(\Suk)~$}} 
\newcommand{\ESLTSuk}{\mbox{$E(S) < E(\Suk)$}}
\newcommand{\ESGTSuk}{\mbox{$E(S) > E(\Suk)~$}}
\newcommand{\ESmkLTS}{\mbox{$E(\Smk) < E(S)$}}
\newcommand{\ESmkGTS}{\mbox{$E(\Smk) > E(S)$}}
where $w_{ij} \in \{\rho,(0,1]\}$.
All proofs in this appendix hold for $0 < w_0 < 1$.
The main idea is that except when $S=\phi$, that is, the initial
state is $\bar{0}$, $w_0$ should play no role in the {\bf sign}
of \ESmkMS or \ESMSuk.
\newline
\begin{lemma}
If a unit switches ON, it cannot switch OFF in any subsequent cycle.
\end{lemma}
{\bf Proof:}
We show by induction that
if a unit $x$ switches ON at time $k$, then for all $i > k$,
(1) $x$ is ON after time $i-1$, and
(2) $d(x)|S_a(i) = |S_a(i)|-1$. \newline
{\bf Basis:} $i=k+1$. 
Since $x$ is switched ON at time $k$,
$x$ is ON after time $k$, and also
$d(x)|S_a(k)=|S_a(k)|$ (see proof of theorem 3
below). Since
$S_a(k+1)=S_a(k) \cup \{x\}$,
$d(x)|S_a(k+1)=|S_a(k+1)|-1$. \newline
{\bf Induction Step:} 
Assume
(1) $x$ is ON after time $j$, for $j > k$, and
(2) $d(x)|S_a(j+1) = |S_a(j+1)|-1$. \newline
After time $j+1$, by condition (2) above, x is still ON.
At time $j+1$, \newline
1. No unit switches. 
Then $d(x)|S_a(j+2) = |S_a(j+2)|-1$. 
\newline
2. A unit $y$, not equal to $x$, switches OFF.
$x$ is {\em adjacent} to $y$ and hence, by $y$ switching OFF, both
$d(x)|S_a(j+1)$ and $|S_a(j+1)|$ are decremented by 1. Hence,
$d(x)|S_a(j+2) = |S_a(j+2)|-1$. \newline
3. A unit, $y$, switches ON. Suppose $y$ is {\em not adjacent}
to $x$. Then by repeating the argument in {\bf Case II, Sub-Case I}
of $``<=''$ proof of theorem 2 below, \ESLTSuk. This
contradicts that $y$ switches ON. Hence $y$ must be {\em adjacent} to
$x$. 
Hence, by $y$ switching ON, both
$d(x)|S_a(j+1)$ and $|S_a(j+1)|$ are incremented by 1. Hence,
$d(x)|S_a(j+2) = |S_a(j+2)|-1$ \newline
This completes the proof $\Box$. 
\newline
\vspace{0.2in}
\newline
{\bf PROOF OF THEOREM 1 (Linear Convergence)} \newline
By Lemma 10, no unit can switch more than twice. Since there
are $N$ units, the number of cycles is $\leq 2 N \Box$. \newline
\vspace{0.2in}
\newline
{\bf PROOF OF THEOREM 2 (Network stable states)} \newline
$``=>''$ We have to show that if $S$ is a stable state, it is
a maximal clique. \newline
{\bf \underline{Case I:}} Suppose $S$ is a non-maximal clique. 
Let
$p_k \in V(G_N)~\backslash~S$ such that 
\Suk is a clique. Then in Eqn (\ref{eq:appendix1}), $w_{ik} > 0$
for all $i \in S$.
Hence \ESGTSuk and
by definition 1, $S$ is not a stable state. \newline
{\bf \underline{Case II:}} Suppose $S$ is not a clique.
From eqn (\ref{eq:appendix2}), for every $k \in S$,
\begin{eqnarray}
\ESmkMS & \leq & \bar{d}_{G[S]}(v) \rho~+~d_{G[S]}(v) \label{eq:thm1pf1}
\end{eqnarray}
{\bf Remark 1}---$\exists k \in S: \bar{d}_{G[S]}(k) \geq 1$.
{\bf Fact 1}--- For all $i \in S: d_{G[S]}(i)<N$. \newline
\newline
{\bf \underline{Case} $ \rho < -N$}. 
For the $k$ that satifies Rem. 1 and by Fact 1, and eqn (\ref{eq:thm1pf1}),
and since $w_0 < 1$, \ESmkLTS.  \newline
{\bf \underline{Case} $\rho < -3 s_m$}. \newline
{\bf \underline{Sub-Case I:}} $|S| < 2 s_m$. 
Again, for the $k$ that satisfies Rem. 1, and by Fact 1, and since
$\rho < -3 s_m$, and eqn (\ref{eq:thm1pf1}), and since $w_0 < 1 < s_m$,
\ESmkLTS.  \newline
{\bf \underline{Sub-Case II:}} $|S| \geq 2 s_m$. 
This is the difficult case. We repeat
a theorem, applicable to any graph, that we have stated and proved in \cite{kn:tr9002}.
\begin{theorem}
Let $G$ be a graph of $N$ vertices and $s_m$ be the size of the maximum clique in $G$.
Then $\exists ~\mbox{a vertex}~v~\in V(G)$ so that $d_G(v) \leq N - \lfloor \frac{N}{s_m} \rfloor$.
\end{theorem}
Let $G[S]$ be our graph. 
By above theorem, 
$\exists ~k~\in S$ so that $d_{G[S]}(k) \leq |S| - \lfloor \frac{|S|}{s_m} \rfloor$.
Hence,
$\bar{d}_{G[S]}(k) \geq \lfloor \frac{|S|}{s_m} \rfloor - 1 $. \newline
{\bf \underline{Claim I:}}
\begin{equation}
\mbox{max}_{n \in \{2 s_m,\ldots,N\}}(\frac{n-\lfloor \frac{n}{s_m} \rfloor }{\lfloor \frac{n}{s_m} \rfloor -1})) \leq 3 (s_m-1) \label{eq:claim1}
\end{equation}
{\bf Fact 1---} From the choices of $n \in \{j s_m,\ldots,(j+1) s_m-1\}$,
with $j > 2$,
the expression inside max of LHS of eqn (\ref{eq:claim1}) has
highest value with $n=(j+1) s_m -1$. \newline
{\bf Fact 2---} From the choices of $n \in \{3 s_m -1,4 s_m-1,  \ldots \}$,
the expression inside max of LHS of eqn (\ref{eq:claim1})
has highest value for $n=3 s_m -1$. Proved by noting, for $j > 2$,
\[ \frac{j s_m -1 -\lfloor \frac{j s_m-1}{s_m} \rfloor }{\lfloor \frac{j s_m-1}{s_m} \rfloor -1} >
\frac{(j+1) s_m -1 -\lfloor \frac{(j+1) s_m-1}{s_m} \rfloor }{\lfloor \frac{(j+1) s_m -1}{s_m} \rfloor -1} 
\] 
Now,
$ \frac{3 s_m -1 -\lfloor \frac{3 s_m-1}{s_m} \rfloor }{\lfloor \frac{3 s_m-1}{s_m} \rfloor -1} = 3(s_m-1) \Box$. \newline
By Claim I, $\rho < -\frac{|S|-\lfloor \frac{|S|}{s_m} \rfloor }{\lfloor \frac{|S|}{s_m} \rfloor -1}$. 
Applying this $\rho$ to eqn (\ref{eq:thm1pf1}), for the $k$ of Thm 6,
and since $w_0 < 1 < 3$, \ESmkLTS .  \newline
In all sub-cases of {\bf Case II}, there exists $k \in S$ such that \ESmkLTS . By defn 1, $S$ is not a stable
state. \newline
``$<=$''. We have to show that if $S$ is a maximal clique, it is a
stable state. \newline
{\bf \underline{Case I:}} $|S|=N$. $V(G_N)$ is the only maximal
clique of $G_N$. Since we have already proved the necessary
condition, it has to be a stable state. \newline
{\bf \underline{Case II:}} $|S| < N$. \newline
{\bf \underline{Sub-Case I:}} Pick any $k \in V(G_N)~\backslash~S$.
$\exists j \in S$ such that $w_{kj}=\rho < -\mbox{min}(3 s_m,N)$.
Since $|S| \leq s_m < N$, from eqn (\ref{eq:appendix1}), and since
$w_0 < 1$,
\ESLTSuk. By defn 1, S is a stable state. \newline
{\bf \underline{Sub-Case II:}} Pick any $k \in S$.
In eqn (\ref{eq:appendix2}), $w_{ik} > 0$ for all $i \in \Smk$.
Hence, \ESmkGTS. 
By defn 1, S is a stable state. \newline
\begin{lemma}
If $S_a(i)$ is a clique, then no unit switches OFF at time $i+1$.
\end{lemma}
{\bf Proof:}
All units receive positive input. Switching any unit OFF will
increase $E$. \newline
\vspace{0.2in}
\newline
{\bf PROOF OF THEOREM 3 (Generic pattern completion dynamics)} \newline
By Induction. \newline
{\bf Basis:}
$S_a(i)$ is a clique. \newline
{\bf Induction step:}
Assume for some $j > i$, $S_a(j)$ is a clique.
By lemma 11, no unit switches OFF at time $j+1$. \newline
1. A unit $k$ switches ON. 
From eqn (\ref{eq:appendix1}),
$w_0 + \sum_{i \in S_a(j)} w_{ik}~>~0$. 
Since $S_a(j)$ is a clique, $|S_a(j)| \leq s_m$. Also, $\rho \leq -s_m$
is given in the theorem statement. Also, $w_0 < 1$.
Hence, for all
$i \in S_a(j)$, $w_{ik} > 0$. Hence $S_a(j+1)$ is
a clique. \newline
2. No unit switches. $S_a(j+1)=S_a(j)$ is a clique. \newline
\newline
\vspace{0.2in}
\newline
{\bf PROOF OF THEOREM 6 (Stable Storage of multi-relations)} \newline
{\bf \underline{Storing multi-relations}} \newline
An n-ary multi-relation on $D_1 \times D_2 \times \ldots \times D_n$
(definition 5) is stored as follows. First, all elements in $D_i$ are
renamed by encoding the domain name (or index $i$) with them. This
ensures that they are distinct. This also allows a tuple to be represented
as an unordered set of its component elements without any loss of
information. We now construct the network.
$D$, the set of symbol units, is equal to
$D_1 \cup D_2 \cup \ldots \cup D_n$.
We choose $k$, the number of size units in the network, to be $n$.
Given a $j$-ary ($j \leq n$) tuple $s=(s_1,\ldots,s_j)$ in
$MR$, we construct $M = \{s_1,\ldots,s_j\}$. Recall that $s_i$
also encodes the name (or index) of $D_i$.
We now apply the storage rule to store $M$ in the network.
Since size units are available,
the network will actually store $M_s = M \cup \{j\}$, $j$ being
the size unit.
We apply the storage rule to all $s \in MR$ in the above way. \newline
{\bf \underline{Notation:}}
We use $M_{st}$ to denote the unordered set representation
(including size unit) of a multi-relation tuple $t$.
Let $V_s = \{1,\ldots,n\}$ denote the set of size units.
We use $D_i$ to also denote the set of units for the symbols in
$D_i$.
\begin{lemma}
After storing an $n$-ary $MR$, for each $D_i,~i=1~\mbox{to}~n$,
$D_i$ is an {\em Independent Set} in $G_N$.
\end{lemma}
{\bf Proof:}
Suppose not. Then $\exists D_i$ and $x,y \in D_i$ that are adjacent,
that is, $w_{xy} > 0$. At least one stored tuple must contain both
$x$ and $y$, which is impossible.
\begin{lemma}
After storing an $n$-ary $MR$, $V_s=\{1,\ldots,n\}$
is an {\em Independent Set} in $G_N$.
\end{lemma}
{\bf Proof:}
Suppose not. Then $\exists i,j \in V_s$ that are adjacent,
that is, $w_{ij} > 0$. At least one stored tuple must contain both
$i$ and $j$, which is again impossible.
\begin{lemma}
After storing an $n$-ary $MR$, {\em every} vertex $i \in V_s$ has the
property that it is ``not adjacent'' to {\em every} vertex in every
$D_j$ for $j > i$.
\end{lemma}
{\bf Proof:}
Suppose not. Then $\exists i \in V_s$ and $v_j \in D_j, j > i$ such
that $i$ and $v_j$ are adjacent,
that is, $w_{i v_j} > 0$. At least one stored tuple must contain both
$i$ and $v_j$. But any tuple that contains $v_j$ must have size
$j > i$ and cannot possibly contain the size unit $i$ also. \newline
{\bf PROOF OF MAIN THEOREM} \newline
We have to show that, after storage of $MR$, the network has a
distinct maximal clique (and hence by theorem 2, a stable state) for 
every $s \in MR$. Suppose this is false.
Let $t \in MR$ with $|t|=i$ be such that $M_{st}$ is not a maximal clique, after storage.
The storage rule stores $M_{st}$ by making it a clique.
Also, since the storage rule only {\em adds} edges in $G_N$, subsequent
storage of other sets does not effect the status of $M_{st}$ as
a clique.
The question is if, after storage of $MR$, this clique is {\em maximal}.
Suppose not. After storage of $MR$,
let $G_N$ have a clique $S' \supset M_{st}$.
Pick $v \in S'~\backslash~M_{st}$. \newline
1. $v \in V_s$. This contradicts Lemma 13. \newline
2. $v \in D_j$ for $j \leq i$. This contradicts Lemma 12. \newline
3. $v \in D_j$ for some $j > i$. This contradicts Lemma 14. \newline
This completes the proof of theorem 5 $\Box$. \newline
\vspace{0.1in}
\newline
{\bf Remark:}
The above proof gives a proof for theorem 5
(stable storage of relations) by specialisation. Cases 1 and 3 
above cannot occur, when we store relations. Case 2 leads to a
contradiction as before. \newline
\vspace{0.2in}
\newline
{\bf PROOF OF LEMMA 6 (Upper bound on stable state size for multi-relations)} \newline
Suppose not. Then there exists a clique in $G_N$ of size $n+2$.
Either two vertices in some $D_i$ are adjacent or two vertices
in $V_s$ are adjacent, contradicting either Lemma 12, or Lemma 13
respectively $\Box$. \newline
\vspace{0.2in}
\newline
{\bf PROOF OF LEMMA 7 (Upper bound on stable state size for relations)} \newline
By Lemma 12, every $D_i$ is an independent set. Hence the
size of the largest maximal clique in $G_N$ (stable state by theorem 2)
is $\leq n$. \newline
\vspace{0.2in}
\newline
{\bf PROOF OF LEMMA 8 (Perfect storage for binary multi-relations)} \newline
By Thm 6, to every tuple of a stored multi-relation $MR$, there corresponds
a distinct maximal clique in $G_N$.
We have to show that because the stored $MR$ is binary,
{\em every} maximal clique of $G_N$ also corresponds to a tuple
of $MR$.
Consider any maximal clique $S$ of $G_N$. \newline
We first note that every unit must be in at least one stored tuple
of $MR$. This makes $|S|=1$ impossible. 
Also, by Lemmas 12 and 13, $|S|$ cannot be greater than $3$.
\newline
{\bf Case 1--- $|S|=2$} 
Let $S=\{x,y\}$. By Lemmas 12-14, the only possibilities are \newline
{\bf (a) $x \in D_1$ and $y=1 \in V_s$} \newline
In this case, $x$ is a 1-tuple in $MR$. Hence $S$ corresponds
to a tuple in $MR$. \newline
{\bf (b) $x \in D_1$ and $y=2 \in V_s$} \newline
There is a 2-tuple $t$ in $MR$ containing $x$. 
But then $M_{st} \supset S$, which contradicts
the assumption that $S$ is a maximal clique. \newline
{\bf (c) $x \in D_2$ and $y=2 \in V_s$} \newline
The same argument as above. \newline
{\bf (d) $x \in D_1$ and $y \in D_2$} \newline
Edge $(x,y)$ of $G_N$ must be in some 2-tuple $t$ in $MR$.
But then $M_{st} \supset S$, which contradicts
the assumption that $S$ is a maximal clique. \newline
{\bf Case 2---$|S|=3$.}
Let $S=\{x,y,z\}$.
By Lemmas 12-14, $x \in D_1$, $y \in D_2$, and $z=2 \in V_s$.
Edge $(x,y)$ of $G_N$ must be in some 2-tuple $t$ in $MR$.
$t=(x,y)$ and hence $M_{st}=\{x,y,2\}$ is equal to $S$. Hence
$t$ is the tuple in $MR$ that corresponds to $S$. \newline
This completes the proof $\Box$. \newline
\vspace{0.2in}
\newline
{\bf PROOF OF LEMMA 9 (Perfect storage for binary relations)} \newline
By Thm 5, to every tuple of a stored relation $R$, there corresponds
a distinct maximal clique in $G_N$.
We have to show that because the stored $R$ is binary,
{\em every} maximal clique of $G_N$ also corresponds to a 2-tuple
of $R$. 
Consider any maximal clique $S$ of $G_N$. \newline
We first note that every unit must be in at least one stored tuple
of $MR$. This makes $|S|=1$ impossible. 
Also by Lemma 12, $|S|$ cannot be greater than $2$.
Let $S=\{x,y\}$. But then edge $(x,y)$ is in some stored tuple $t$ in
$R$. Since $|t|=2$, $t=(x,y)$. Hence $S$ corresponds to $t$ $\Box$. \newline
}
\begin{center}
\setlength{\unitlength}{0.0125in}
\begin{picture}(511,738)(57,74)
\thicklines
\put(161,674){\circle{24}}
\put(162,727){\circle{24}}
\put(163,777){\circle{24}}
\put(427,672){\circle{24}}
\put(428,725){\circle{24}}
\put(429,775){\circle{24}}
\put(300,776){\circle{24}}
\put(299,726){\circle{24}}
\put(298,673){\circle{24}}
\put(424,458){\circle{24}}
\put(424,532){\circle{24}}
\put(296,532){\circle{24}}
\put(296,458){\circle{24}}
\put(161,458){\circle{24}}
\put(161,532){\circle{24}}
\put(510,269){\circle{24}}
\put(509,200){\circle{24}}
\put(514,341){\circle{24}}
\put(424,319){\circle{24}}
\put(424,245){\circle{24}}
\put(293,244){\circle{24}}
\put(293,318){\circle{24}}
\put(161,332){\circle{24}}
\put(160,282){\circle{24}}
\put(159,229){\circle{24}}
\multiput(494,178)(9.25000,0.00000){5}{\makebox(0.4444,0.6667){\tenrm .}}
\multiput(494,365)(9.25000,0.00000){5}{\makebox(0.4444,0.6667){\tenrm .}}
\multiput(494,178)(0.00000,9.84211){20}{\makebox(0.4444,0.6667){\tenrm .}}
\multiput(531,178)(0.00000,9.84211){20}{\makebox(0.4444,0.6667){\tenrm .}}
\multiput(403,197)(10.00000,0.00000){5}{\makebox(0.4444,0.6667){\tenrm .}}
\multiput(403,357)(10.00000,0.00000){5}{\makebox(0.4444,0.6667){\tenrm .}}
\multiput(403,197)(0.00000,9.41176){18}{\makebox(0.4444,0.6667){\tenrm .}}
\multiput(443,197)(0.00000,9.41176){18}{\makebox(0.4444,0.6667){\tenrm .}}
\multiput(272,198)(10.00000,0.00000){5}{\makebox(0.4444,0.6667){\tenrm .}}
\multiput(272,358)(10.00000,0.00000){5}{\makebox(0.4444,0.6667){\tenrm .}}
\multiput(272,198)(0.00000,9.41176){18}{\makebox(0.4444,0.6667){\tenrm .}}
\multiput(312,198)(0.00000,9.41176){18}{\makebox(0.4444,0.6667){\tenrm .}}
\multiput(404,428)(10.25000,0.00000){5}{\makebox(0.4444,0.6667){\tenrm .}}
\multiput(404,574)(10.25000,0.00000){5}{\makebox(0.4444,0.6667){\tenrm .}}
\multiput(404,428)(0.00000,9.73333){16}{\makebox(0.4444,0.6667){\tenrm .}}
\multiput(445,428)(0.00000,9.73333){16}{\makebox(0.4444,0.6667){\tenrm .}}
\multiput(275,430)(10.25000,0.00000){5}{\makebox(0.4444,0.6667){\tenrm .}}
\multiput(275,576)(10.25000,0.00000){5}{\makebox(0.4444,0.6667){\tenrm .}}
\multiput(275,430)(0.00000,9.73333){16}{\makebox(0.4444,0.6667){\tenrm .}}
\multiput(316,430)(0.00000,9.73333){16}{\makebox(0.4444,0.6667){\tenrm .}}
\multiput(141,429)(10.25000,0.00000){5}{\makebox(0.4444,0.6667){\tenrm .}}
\multiput(141,575)(10.25000,0.00000){5}{\makebox(0.4444,0.6667){\tenrm .}}
\multiput(141,429)(0.00000,9.73333){16}{\makebox(0.4444,0.6667){\tenrm .}}
\multiput(182,429)(0.00000,9.73333){16}{\makebox(0.4444,0.6667){\tenrm .}}
\multiput(141,196)(10.00000,0.00000){5}{\makebox(0.4444,0.6667){\tenrm .}}
\multiput(141,356)(10.00000,0.00000){5}{\makebox(0.4444,0.6667){\tenrm .}}
\multiput(141,196)(0.00000,9.41176){18}{\makebox(0.4444,0.6667){\tenrm .}}
\multiput(181,196)(0.00000,9.41176){18}{\makebox(0.4444,0.6667){\tenrm .}}
\multiput(409,647)(10.00000,0.00000){5}{\makebox(0.4444,0.6667){\tenrm .}}
\multiput(409,807)(10.00000,0.00000){5}{\makebox(0.4444,0.6667){\tenrm .}}
\multiput(409,647)(0.00000,9.41176){18}{\makebox(0.4444,0.6667){\tenrm .}}
\multiput(449,647)(0.00000,9.41176){18}{\makebox(0.4444,0.6667){\tenrm .}}
\multiput(278,646)(10.00000,0.00000){5}{\makebox(0.4444,0.6667){\tenrm .}}
\multiput(278,806)(10.00000,0.00000){5}{\makebox(0.4444,0.6667){\tenrm .}}
\multiput(278,646)(0.00000,9.41176){18}{\makebox(0.4444,0.6667){\tenrm .}}
\multiput(318,646)(0.00000,9.41176){18}{\makebox(0.4444,0.6667){\tenrm .}}
\multiput(142,647)(10.00000,0.00000){5}{\makebox(0.4444,0.6667){\tenrm .}}
\multiput(142,807)(10.00000,0.00000){5}{\makebox(0.4444,0.6667){\tenrm .}}
\multiput(142,647)(0.00000,9.41176){18}{\makebox(0.4444,0.6667){\tenrm .}}
\multiput(182,647)(0.00000,9.41176){18}{\makebox(0.4444,0.6667){\tenrm .}}
\put(460,226){\line( 1, 1){ 38}}
\put(172,226){\line( 1, 0){288}}
\put(173,284){\line( 1, 0){323}}
\put(305,246){\line( 6, 1){190.865}}
\put(305,321){\line( 4,-1){192}}
\put(436,246){\line( 3, 1){ 61.500}}
\put(434,313){\line( 5,-3){ 63.824}}
\put(169,223){\line( 1, 0){328}}
\put(305,242){\line( 5,-1){191.731}}
\put(172,338){\line( 1, 0){329}}
\put(176,776){\line( 1, 0){111}}
\put(312,776){\line( 1, 0){104}}
\put(173,769){\line( 3,-1){114}}
\put(312,725){\line( 1, 0){103}}
\put(174,772){\line( 6,-1){242.270}}
\put(174,673){\line( 1, 0){111}}
\put(311,672){\line( 1, 0){104}}
\put(171,786){\line( 6, 1){126.487}}
\put(299,798){\line( 6,-1){120.811}}
\put(171,669){\line( 6,-1){128.919}}
\put(301,654){\line( 6, 1){112.216}}
\put(174,531){\line( 1, 0){110}}
\put(309,531){\line( 1, 0){102}}
\put(171,526){\line( 2,-1){115.200}}
\put(307,462){\line( 5, 3){105.735}}
\put(171,464){\line( 2, 1){115.600}}
\put(306,524){\line( 2,-1){110.400}}
\put(173,528){\line( 4,-1){241.412}}
\put(173,460){\line( 4, 1){240.941}}
\put(170,540){\line( 5, 1){125}}
\put(295,565){\line( 5,-1){120}}
\put(171,287){\line( 4, 1){111.294}}
\put(172,230){\line( 6, 1){108}}
\put(304,249){\line( 5, 3){107.500}}
\put(169,235){\line( 3, 1){244.200}}
\put(305,317){\line( 5,-3){107.941}}
\put(172,282){\line( 6,-1){239.514}}
\put( 57, 84){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twltt Fig 3 - Examples of storing vectors, relations, multi-relations}}}
\put( 64,140){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twltt 3.3 - Gn after storing multi-relation of words  a, do, car, dot}}}
\put( 68,391){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twltt 3.2 - Gn after storing vectors  101, 011, 110}}}
\put( 66,601){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twltt 3.1 - Gn after storing relation  {(a,1,A),(a,2,B),(c,3,C)}}}}
\put(160,774){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twltt a}}}
\put(159,723){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twltt b}}}
\put(157,671){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twltt c}}}
\put(297,772){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twltt 1}}}
\put(296,721){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twltt 2}}}
\put(295,668){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twltt 3}}}
\put(426,771){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twltt A}}}
\put(426,720){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twltt B}}}
\put(423,668){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twltt C}}}
\put(149,548){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twltt 1-1}}}
\put(282,548){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twltt 1-2}}}
\put(411,547){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twltt 1-3}}}
\put(150,473){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twltt 0-1}}}
\put(285,473){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twltt 0-2}}}
\put(412,472){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twltt 0-3}}}
\put(155,328){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twltt a1}}}
\put(153,279){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twltt c1}}}
\put(152,226){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twltt d1}}}
\put(285,314){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twltt a2}}}
\put(285,240){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twltt o2}}}
\put(416,314){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twltt t3}}}
\put(418,241){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twltt r3}}}
\put(510,338){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twltt 1}}}
\put(506,196){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twltt 2}}}
\put(507,264){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twltt 3}}}
\end{picture}
\end{center}
\end{document}
