Let be a semantic network retrieval model. The set
consists of
objects each of which is a node in a directed graph G with two types of arcs: isa
and partof. An isa-arc denotes the subclass-superclass relationship
between the nodes it connects; a partof-arcs denotes the part-whole
relationship between the nodes (Fitzgerald 1995). Let
be the
matrix such
that
if there is an isa-arc from
and
, and
,
if there is no such arc. Let
be a similar matrix for the partof-relationship.
An object
abstracts an object
iff G has a path of isa-arcs
from
to
. When
abstracts
,
is
an abstraction of
. An object
specializes an
object
iff G has a path of isa-arcs from
to
.
Thus,
abstracts
iff
specializes
.
Any object both abstracts and specializes itself.
Associated with each node is a single set of labels. A label is a sequence
of elements such that for all i,
. Thus, labels may contain not only
tokens but also object ids. If
, then
is the set of labels
associated with
. If
, and
,
. An expectation
is a 3-tuple
such that
. For example, if
, then
,
,
,
and
are expectations. Intuitively, an expectation reflects how completed a
label is with respect to an object. If
is an expectation,
,
,
,
and key(z) = head(ecseq(z)).
, where
is the set of labels associated with
,
,
and
. Note that
and
can be empty. For example,
if
,
. Let
and
. The object
similarity between
and
is
, where
,
,
completes
,
and
. The object
activates
the object
iff there exists a label
and a label
such that
completes
.
If there is no
such that
completes
, then
.
Let [x] be a label associated with a node . The token closure of [x],
, is the set of all token sequences that complete [x]. For example, let
and
be two nodes such that
and
, where all
.
Then
. An algorithm for computing token closures is given in Listing 1 of the
Appendix. Intuitively, the token closure of a label is the set of all token sequences
through which the label can be completed, and, consequently, the label's node activated.
For example, the first two elements of
complete
associated in
,
thus activating
. When
is activated,
is advanced one element to
the right, which allows the rest of the label, i.e.,
to be completed by the
last two elements of
, thus activating
. The token
closure of a node
,
, is the union of the
token closures of its labels. Thus, the token closure of a node is the set of all token
sequences that can possibly activate the node. The union of the token closures of nodes in
is called
-closure. Formally,
-closure
.