Helmut Schumacher
Abstract
Previous approaches to the problem of automatically converting decision tables to computer programs have been based on decomposition. At any stage, one condition is selected for testing, and two smaller problems (decision tables with one less condition) are created. An optimal program (with respect to average execution time or storage space, for example) is located only through implicit enumeration of all possible decision trees using a technique such as branch-and-bound. The new approach described in this paper uses dynamic programming to synthesize an optimal decision tree from which a program can be created. Using this approach, the efficiency of creating an optimal program is increased substantially, permitting generation of optimal programs for decision tables with as many as ten to twelve conditions.
- 1 Humby, E. Programs From Decision Tables. American Elsevier, New York, 1973.Google Scholar
- 2 Pooch, U.W. Translation of decision tables. Computing Surveys 6, 2 (June 1974), 125-51. Google ScholarDigital Library
- 3 Woods, C.J., and Hawes, M.K. Optimized code generation from extended-entry decision tables. SIGPLAN Notices (ACM Newsletter) 6, 8 (Sep. 1971), 74-80. Google ScholarDigital Library
- 4 Muthukrishnan, C.R., and Rajaraman, V. On the conversion of decision tables to computer programs. Comm. ACM 13, 6 (June 1970), 347-51. Google ScholarDigital Library
- 5 Schurnacher, H. The synthesis of optimal decision trees from decision tables. M.Sc. Th., Rep. CSRG-46, Computer Systems Research Group, U. of Toronto, Dec. 1974.Google Scholar
- 6 Kirk, G.W. Use of decision tables in computer programming. Comm. ACM 8, 1 (Jan. 1965), 41-43. Google ScholarDigital Library
- 7 King, P.J.H. Conversion of decision tables to computer programs by the rule mask technique. Comm. ACM 9, 11 (Nov. 1966), 796-801. Google ScholarDigital Library
- 8 Pollack, S.L. Conversion of limited-entry decision tables to computer programs. Comm. ACM 8, 11 (Nov. 1965), 677-82. Google ScholarDigital Library
- 9 Rabin, J. Conversion of limited-entry decision tables into optimal decision trees: fundamental concepts. SIGPLAN Notices (ACM Newsletter) 6, (Sep. 1971), 68-71. Google ScholarDigital Library
- 10 Shwayder, K. Conversion of limited-entry decision tables to computer programs-a proposed modification to Pollack's algorithm. Comm. ACM 14, 2 (Eeb. 1971), 69-73. Google ScholarDigital Library
- 11 Shwayder, K. Extending the information theory approach to converting limited-entry decision tables to computer programs. Comm. ACM 17, 9 (Sep. 1974), 532-37. Google ScholarDigital Library
- 12 Ganapathy, S., and Rajaraman, V. Information theory applied to the conversion of decision tables to computer programs. Comm. ACM 16, 9 (Sep. 1973), 532-39. Google ScholarDigital Library
- 13 Reinwald, L.T., and Soland, R.M. Conversion of limited-entry decision tables to optimal computer programs-I: Minimum average processing time. d. ACM 13, 3 (July 1966), 339-58. Google ScholarDigital Library
- 14 Reinwald, L.T., and Soland, R.M. Conversion of limited-entry decision tables to optimal computer programs-II: Minimum storage requirement. J. ACM 14, 4 (Oct. 1967), 742-55. Google ScholarDigital Library
- 15 Yasui, T. Conversion of decision tables into decision trees. Ph.D. thesis, Rep. 501, U. of Illinois, Feb. 1972. Google ScholarDigital Library
- 16 Myers, H.J. Compiling optimized code from decision tables. IBM Y. Res. andDev. 16, 5 (Sep. 1972), 489-503.Google Scholar
- 17 Jarvis, J.M. An analysis of programming via decision table compilers. SIGPLAN Notices (ACM Newsletter) 6, 8 (Sep. 1971), 20-32. Google ScholarDigital Library
- 18 Verhelst, M. The conversion of limited-entry decision tables to optimal and near-optimal flowcharts: two new algorithms. Comm. ACM 15, 11 (Nov. 1972), 974-80. Google ScholarDigital Library
- 19 Bayes, A.J. A Dynamic programming algorithm to optimise decision table code. Australian Computer J. 5, 2(May 1973), 77-79.Google Scholar
Recommendations
Optimal conversion of extended-entry decision tables with general cost criteria
A general dynamic programming algorithm for converting limited, extended, or mixed entry decision tables to optimal decision trees is presented which can take into account rule frequencies or probabilities, minimum time and/or space cost criteria, ...
Combining decision rules in a decision table
The techniques for minimizing logic circuits are applied to the simplification of decision tables by the combining of decision rules. This method is logically equivalent to the Quine-McCluskey method for finding prime implicants. If some of the decision ...
Conversion of decision tables to efficient sequential testing procedures
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 ...
Comments