Knowledge Representation: Term Project 1
Term Project 1: Implementing Formula-Augmented Networks
Due: Monday, May 17, 1999 (Friday May 14 for anyone graduating)
Questions to firstname.lastname@example.org
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,
"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
- 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
The small sample rules file can be found
Answers to frequently asked questions can be found
You can find a write-up of the Stein algorithm
and of the FAN-traversal algorithm
Back to web page for KR course