Propositional production rules, decision trees, and decision tables are knowledge representations frequently used in the representation of expert systems’ knowledge bases. They are equivalent in the sense that an implementation using one representation can be algorithmically translated into another implementation that preserves the original implementation’s input/output behavior. It is convenient to use different representations for different purposes. (For example, one is used as a way of representing the knowledge to human users, whereas another is used to provide an efficient implementation of the expert system.) However, as Colomb points out, the translated representation is often significantly larger than the original representation. He explains why this is the case and provides a way of eliminating this problem.

Colomb defines the size of an implementation using a particular knowledge representation as the number of rules for a rule-based system, the number of leaf nodes for a decision tree, and the number of rows for a decision table. He then shows that the increased size, which he calls the inflation, of a translated representation results from the fact that parts of the translated representation are not needed. For example, one might begin with an expert system implemented using production rules, where all of the rules are exercised by the cases considered by the system. After translating the system into an equivalent system implemented using a decision table, the table will have many rows that are not exercised by the cases. Colomb shows that the inflation that occurs in the various translation processes is a result of the fact that the translated representations are constructed as total functions, as opposed to partial functions, on the attribute space defined by the variables considered by the expert system. Colomb’s solution, then, is to construct the knowledge representation implementations as partial functions on the attribute space.

This clear, well-written paper should interest researchers in the area of knowledge representation.