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 .