Conversion of decision tables to efficient sequential testing procedures

ABSTRACT

Sequential testing procedures for checking the rule-applicability of the decision tables encountered in practice are usually found to be minimum-path-length trees. On the basis of this observation, an algorithm is developed for converting decision tables to efficient decision trees. A criterion is defined for estimating the minimum expected cost of the tree in terms of rule probabilities and condition-testing costs and is utilized in arriving at the efficient decision tree. The algorithm is applicable to general limited-entry decision tables and can also be employed for manual coding.

REFERENCES

• 1: J. F. Egler, A procedure for converting logic table conditions into an efficient sequence of test instructions, Communications of the ACM, v.6 n.9, p.510-514, Sept. 1963 [doi>10.1145/367593.367595]
• 2: S. Ganapathy , V. Rajaraman, Information theory applied to the conversion of decision tables to computer programs, Communications of the ACM, v.16 n.9, p.532-539, Sept. 1973 [doi>10.1145/362342.362348]
• 3: P. J. H. King, Conversion of decision tables to computer programs by rule mask techniques, Communications of the ACM, v.9 n.11, p.796-801, Nov. 1966 [doi>10.1145/365876.365896]
• 4: H. W. Kirk, Use of decision tables in computer programming, Communications of the ACM, v.8 n.1, p.41-43, Jan. 1965 [doi>10.1145/363707.363725]
• 5: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 6: Solomon L. Pollack, Conversion of limited-entry decision tables to computer programs, Communications of the ACM, v.8 n.11, p.677-682, Nov. 1965 [doi>10.1145/365660.365681]
• 7: Lewis T. Reinwald , Richard M. Soland, Conversion of Limited-Entry Decision Tables to Optimal Computer Programs I: Minimum Average Processing Time, Journal of the ACM (JACM), v.13 n.3, p.339-358, July 1966 [doi>10.1145/321341.321343]
• 8: Helmut Schumacher , Kenneth C. Sevcik, The synthetic approach to decision table conversion, Communications of the ACM, v.19 n.6, p.343-351, June 1976 [doi>10.1145/360238.360245]
• 9: Sethi, I.K., and Chatterjee, B. Efficient decision tree design for discrete variable pattern recognition problems. Pattern Recognition 9, 4 (1977), 197-206.
• 10: Keith Shwayder, Conversion of limited-entry decision tables to computer programs—a proposed modification to Pollack's algorithm, Communications of the ACM, v.14 n.2, p.69-73, Feb. 1971 [doi>10.1145/362515.362518]
• 11: M. Verhelst, The conversion of limited-entry decision tables to optimal and near-optimal flowcharts: two new algorithms, Communications of the ACM, v.15 n.11, p.974-980, Nov. 1972 [doi>10.1145/355606.361883]

INDEX TERMS

Keywords:
decision tables, decision trees, sequential testing procedures