Information theory applied to the conversion of decision tables to computer programs

ABSTRACT

Using ideas from information theory, this paper develops a heuristic algorithm that converts a limited entry decision table to a tree structured computer program with near minimum average processing time. The method is applicable to any limited entry decision table and does not require that actions have single rules or that the cost of testing conditions be equal. It is thus more general than the previously published heuristic algorithms. Compared to the optimal algorithm of Reinwald and Soland, this algorithm is easy to code and takes a much smaller translation time; it is thus felt that it is more useful in practice. The algorithm is well suited for manual conversion of decision tables to flowcharts.

REFERENCES

• 1: 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]
• 2: Montalbano, M. Tables, flowcharts and program logic. IBM Systems J. (Sept. 1962), 51-63.
• 3: 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]
• 4: 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]
• 5: King, P.J.H. Decision tables. Computer J. 10, 2 (Aug. 1967), 135-142.
• 6: 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]
• 7: Little, J.D.C., Murty, K.G., Sweeney, D.W., and Kareb, C. An algorithm for the travelling salesman problem. Operations Research 11 (1963), 972-989.
• 8: CaldweU, S.H. Switching Circuits and Logical Design. Wiley, New York, 1960.
• 9: Fano, R.M. Transmission ofblJbrmation. MIT Press and Wiley, New York, 1963.
• 10: Ganapathy, S. Information theory applied to decision tables. M. Tech Th., Indian Institute of Technology, Kanpur, India, (July 1969).
• 11: 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]
• 12: 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]
• 13: Rajaraman, V. Computer Programming hz Fortran IV. Prentice-Hall of India Ltd., New Delhi, 197l, 132-147.
• 14: lbramshah, M., and Rajaraman, V. A fast rule mask algorithm for the conversion of decision tables to computer programs. Techn. Rept. Computer Centre, Indian Institute of Technology, Kanpur, India, 1971.

INDEX TERMS

Keywords:
decision tables, information measure, optimum computer programs