The synthetic approach to decision table conversion

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.

REFERENCES

• 1: Humby, E. Programs From Decision Tables. American Elsevier, New York, 1973.
• 2: Udo W. Pooch, Translation of Decision Tables, ACM Computing Surveys (CSUR), v.6 n.2, p.125-151, June 1974 [doi>10.1145/356628.356630]
• 3: C. Geoffrey Woods , Mary K. Hawes, Optimized code generation from extended-entry decision tables, ACM SIGPLAN Notices, v.6 n.8, p.74-80, September 1971 [doi>10.1145/953368.953378]
• 4: C. R. Muthukrishnan , V. Rajaraman, On the conversion of decision tables to computer programs, Communications of the ACM, v.13 n.6, p.347-351, June 1970 [doi>10.1145/362384.362390]
• 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.
• 6: 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]
• 7: 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]
• 8: 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]
• 9: Jonas Rabin, Conversion of limited-entry decision tables into optimal decision trees: fundamental concepts, ACM SIGPLAN Notices, v.6 n.8, p.68-74, September 1971 [doi>10.1145/953368.953377]
• 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: Keith Shwayder, Extending the infomation theory approach to converting limited-entry decision tables to computer programs, Communications of the ACM, v.17 n.9, p.532-537, Sept. 1974 [doi>10.1145/361147.361117]
• 12: 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]
• 13: 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]
• 14: Lewis T. Reinwald , Richard M. Soland, Conversion of Limited-Entry Decision Tables to Optimal Computer Programs II: minimum storage requirement, Journal of the ACM (JACM), v.14 n.4, p.742-756, Oct. 1967 [doi>10.1145/321420.321433]
• 15: Toshio Yasui, Conversion of decision tables into decision trees, 1972
• 16: Myers, H.J. Compiling optimized code from decision tables. IBM Y. Res. andDev. 16, 5 (Sep. 1972), 489-503.
• 17: J. M. Jarvis, An analysis of programming via decision table compilers, ACM SIGPLAN Notices, v.6 n.8, p.20-32, September 1971 [doi>10.1145/953368.953372]
• 18: 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]
• 19: Bayes, A.J. A Dynamic programming algorithm to optimise decision table code. Australian Computer J. 5, 2(May 1973), 77-79.

INDEX TERMS

Keywords:
decision tables, decision trees, dynamic programming, optimal programs