Semantic Inheritance Networks

A path is a sequence of links in a graph G, with the final node of each link being the initial node of the next, where all the links, with the possible exception of the last one, are positive. A generalized path is a sequence of links that can contain negative links anywhere, and more than one. Each path has both an initial node and a final node. A path can be taken as representing an assertion about an individual: that the individual corresponding to the initial node belongs to the category corresponding to the final node. The degree of a path is the length of the longest generalized path connecting the path's initial node to its final node.

Horty, Thomason, and Touretzky define the relation of support between graphs (cognitive states) and paths (assertions) by mathematical induction on the degree of the path. Direct links (paths of length one) are always supported by the graph.

1. If σ is a positive path, x → σ¹ → u → y, then G supports σ iff:
   1. G supports path x → σ¹ → u.
   2. u → y is a direct link in G.
   3. The negative link x →⁄ y does not belong to G.
   4. for all v, τ such that G supports x → τ → v, with the negative link v →⁄ y in G, there exist z, τ¹, τ² such that z → y is in G, and either z = x, or G supports the path x → τ¹ → z → τ² → v.
2. If σ is a negative path, x → σ¹ → u →⁄ y, then G supports σ iff:
   1. G supports path x → σ¹ → u.
   2. u →⁄ y is a direct negative link in G.
   3. The positive link x → y does not belong to G.
   4. for all v, τ such that G supports x → τ → v, with the positive link v → y in G, there exist z, τ¹, τ² such that z →⁄ y is in G, and either z = x, or G supports the path x → τ¹ → z → τ² → v.

The definition ensures that each potentially conflicting path be preempted by a path with a specificity-based priority.