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:
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:
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