Given the number of words of computer storage required by the individual tests in a limited-entry decision table, it is sometimes desirable to find an equivalent computer program with minimum total storage requirement. In this paper an algorithm is developed to do this. The rules in the decision table are grouped into action sets, so that several rules with the same actions need not be distinguished. Moreover, if certain combinations of conditions can be excluded from consideration, the algorithm will take advantage of this extra information. The algorithm is initially developed for computer programs possessing a treelike form and then extended to a wider class of programs. The algorithm can be combined with one which finds an equivalent computer program with minimum average processing time, and thus used to find an equivalent computer program which minimizes a cost function which is nondecreasing in both average processing time and total storage requirement.

This paper begins with a brief description of desicion tables, and then presents a discussion of alternative expressions for them as sequential testing procedures for computer implementation and as Boolean functions. An algorithm is developed which, in a finite number of steps, will convert any given limited entry decision table into an “optimal” computer program, one with minimum average processing time. The algorithm is more general than procedures previously developed and guarantees optimality of the resultant computer program. Previous procedures required two distinct steps and gave no assurance of overall optimality. Computer implementation of the algorithm is also discussed.