Conversion of Limited-Entry Decision Table to Optimal Computer Programs: Ii. Minimum Storage Requirement

摘要

The paper presents an algorithm that will convert any given limited-entry decision table (LEDT) into a computer program with minimum total storage requirement. It is assumed that the storage requirements of the individual tests in the decision table are given. The report contains a brief description of LEDTs and their conversion into sequential testing procedures; develops the algorithm and gives an illustrative example; extends the algorithm to the case in which advantage is to be taken of the fact that certain combinations of conditions can be excluded from consideration; extends the algorithm to computer programs that do not necessarily have a treelike form; and briefly reviews an algorithm that will convert a LEDT into a computer program with minimum average processing time. Given an overall cost function that is nondecreasing in both average processing time and total storage requirement, it is then shown how the two algorithms may be combined to find a computer program with minimum overall cost. The final section briefly discusses an alternative conversion procedure proposed by Kirk. (Author)