Questions to leora@watson.ibm.com

Last modified: May 12, 1999.

Below, a write-up of the two main algorithms needed for the FANs program. First, the preprocessing algorithm to determine the specificity extension at a node in a network (Stein's algorithm, somewhat modified). Second, the FANs traversal algorithm (the algorithm from (Morgenstern, 1998)).

PREPROCESSING ALGORITHM (Stein, AIJ, 1992) (somewhat modified to deal with redundant links)

Stein's algorithm takes a network and a particular node, called a focus node, and processes the network by removing all preempted edges. Once the network is preprocessed, all preempted (defeated) paths are removed. Then, one can easily answer the question is there an undefeated path (positive or negative) between the focus node a and some node b , for any node b in the network, by just checking whether there is a path from a to b.

Basic idea of Stein's algorithm:
For a focus node a, consider all nodes that are a-reachable, i.e., that can be reached from a. (A node x is a-reachable from a if there is some (positive or negative) path from a to x.)
Step 1: Do a topological sort of those nodes.
Step 2: Now, build up the graph node by node, in topological order.
Start off with just the nodes, no edges. The algorithm will add the correct edges as it goes along.
For each node x,
(loop for step2)
consider all the edges that end in x. (Note that there are no such edges for the first node, the focus node a.) For all nodes other than the focus node, there are two cases:

1. Case 1: There is only one edge that ends in x. In this case, just add the edge to the graph.
2. Case2: There is more than one edge that ends in x. In this case, do a reverse topological sort of all edges. This means that you will end up with a sequence of edges b1-x, b2-x, ..., bn-x, where bi+1 is always at least as specific as bi (or to look at it another way, bi+1 is at least as close to the focus node as bi).
   Inner Loop:
   Now start looking at the edges in this reverse topological order. Starting with the first two edges in this reverse order, do a pairwise comparison of edges, as described below, until there are no more edges.
   For any two edges, there are two cases:
   • Inner Case 1: The two edges bj-x and bi-x are of opposite sign. This is the case of one path preempting another. In this case, discard the first edge (the edge which comes from a more general node), and keep the second edge.
   • Inner Case 2: The two edges bj-x and bi-x are of the same sign. This is the case where we may have redundant paths. We check for redundant paths. Let us assume (without loss of generality) that bi is more specific than bj. Then, we must check the graph that we have thus far constructed, and see if there is a path bi-c1-...-cn-bj-x that is of the same sign as bi-x. In this case, the edge bi-x is redundant. So we discard bi-x (the edge which comes from a more specific node), and keep the first edge, bj-x.

FAN TRAVERSAL ALGORITHM: (Morgenstern, AIJ, 1998)

Basic idea:
We have a FAN (a formula-augmented network), an inheritance network with exceptions in which rules (logical formulas) are attached to the nodes. FANs include a set of background rules. We are interested in determining which rules apply to (can be inherited at) a focus node n. Call this set Psi(n).
Step 1:Preprocess the network (at the focus node) as described above to remove preempted and redundant links.
Step 2:To start, put the background rules in Psi(n). Now start traversing the specificity extension of n, starting at n.
LOOP FOR TRAVERSING A FAN AT A NODE x:

1. Whenever you visit a node x, take the pmcs of Apply(n) and the node you are visiting. (Remember, n is the focus node.) The pmcs is the preferred maximally consistent subset. See below for instructions on one way of determining a pmcs.
2. Once you have visited a node x, mark it as visited. Now you must continue the traversal.
   Case 1: x is a leaf. Return.
   Case 2: x has one parent, y. Go to y, and Traverse the FAN at node y.
   Case 3: x has more than one parent. Do a topological sort of all links x-yi, and in topological order, Traverse the FAN at these nodes.

Determining a pmcs (preferred maximally consistent subset) of two sets
The following is an easy method to determine pmcs(a.b). By convention, the first set is considered "preferred." Also by assumption, both sets are themselves consistent.

One easy method is the following greedy algorithm. Put into pmcs(a,b) all rules of a. Now put in as much of b as you can. Specifically, order the rules in b in some (arbitrary) sequence. Now, examine each rule in turn. If you can add it to pmcs, and the resulting set is consistent, add it; otherwise discard it. The final set is guaranteed to be a maximally consistent subset of a union b, although it may not be minimal in terms of cardinality.

Back to web page for KR course