Due: Monday, May 17, 1999 (Friday May 14 for anyone graduating)
Questions to leora@watson.ibm.com

The task here is to implement Formula-Augmented Networks, a knowledge representation structure that allows one to reason about the inheritance of logical formulas. They are described in detail in a number of papers, including
Leora Morgenstern: "Inheritance Comes of Age: Applying Nonmonotonic Techniques to Problems in Industry" ( the long journal paper), the shorter conference paper, and an earlier paper, Inheriting Well-formed Formulae in a Formula-Augmented Semantic Network. This project can be divided into the following subtasks:

• Constructing the data structure for a FAN. A FAN is best thought of as an inheritance network with exceptions (basically a directed acyclic graph with two kinds of links, isa links and cancels links), where each node may have attached to it a set of logical formulas, and for each node with more than two parents, the set of links from the node to its parents may be ordered in a partial or total order. Also attached to the FAN data structure is a set of formulas, known as the background information, which can be thought of as formulas that are true at every node.
• Implementing Stein's algorithm for skeptical inheritance (Artificial Intelligence 1992).
• Implementing a function which takes two sets and determines a preferred maximally consistent subset of the two sets. The algorithm to determine a preferred maximally consistent subset is relatively straightforward. Given two sets of formulas F1 and F2, attached respectively to nodes N1 and N2, where N1 is preferred to N2 (either through specificity or path preference), F1 is preferred to F2. Assuming F1 is preferred to F2, one has to
  • check whether F1 and F2 are mutually inconsistent. This is done using a technique known as resolution. Resolution is refutation complete, which means that it will determine when a set is inconsistent.
  • If inconsistent, find a maximally consistent subset F2' of F2 such that F1 and F2' are mutually consistent.
• Implementing the algorithm to traverse a FAN and determine the set of rules which apply to a node as described in (Morgenstern, 1998).

The following functionality must be exhibited.

• Given a node name, display the node, its parents, and its children. (Displaying several levels of ancestors and descendants is preferred.) Text displays are okay here; no need for graphical displays.
• Given two nodes a and x, where a is lower in the hierarchy than x, determine if one can conclude that a isa x, using ideally skeptical inheritance (Stein's algorithm).
• Given a node name, display the set of formulas attached to the node.
• Given a node, display the set of formulas that apply to the node. Show the trace of the steps used in determining the answer.

Language to be used: Any well-known language such as C, C++, Java, Lisp, or Prolog is okay. If you have questions, check with Stathis or me.

Test data: will be provided. Rules will already be in first-order predicate calculus, so you will not have to translate from English to first-order logic for this project.

You can find sample input for the network structure (nodes, isa and cancels links) here. An explanation of this input file can be found here. The small sample rules file can be found here. Answers to frequently asked questions can be found here.

You can find a write-up of the Stein algorithm and of the FAN-traversal algorithm here.

Back to web page for KR course