Extending the infomation theory approach to converting limited-entry decision tables to computer programs

ABSTRACT

This paper modifies an earlier algorithm for converting decision tables into flowcharts which minimize subsequent execution time when compiled into a computer program. The algorithms considered in this paper perform limited search and, accordingly, do not necessarily result in globally optimal solutions. However, the greater search effort needed to obtain a globally optimal solution for complex decision tables is usually not justified by sufficient savings in execution time. There is an analogy between the problem of converting decision tables into efficient flowcharts and the well-understood problem in information theory of noiseless coding. The results of the noiseless coding literature are used to explore the limitations of algorithms used to solve the decision table problem. The analogy between the two problems is also used to develop improvements to the information algorithm in extending the depth of search under certain conditions and in proposing additional conditions to be added to the decision table. Finally, the information algorithm is compared with an algorithm proposed in a recent paper by Verhelst.

REFERENCES

• 1: Ash, R. information Theory, Wiley, New York, 1965.
• 2: Ned Chapin, Parsing of decision tables, Communications of the ACM, v.10 n.8, p.507-511, Aug. 1967 [doi>10.1145/363534.363557]
• 3: 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]
• 4: Huffman, D.A. A method for the construction of minimum redundancy codes. Proc. IRE 40, 10 (Oct. 1952), 1098-1101.
• 5: P. J. H. King , R. G. Johnson, Comments on the algorithms of Verhelst for the conversion of limited-entry decision tables to flowcharts, Communications of the ACM, v.17 n.1, p.43-45, Jan. 1974 [doi>10.1145/360767.360807]
• 6: Pollack, S.L., Hicks, H.T., and Harrison, W.J. Decision Tables: Theory and Practice. Wiley, New York, 1971.
• 7: 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]
• 8: Shwayder, K., Kenney, A.A., and Ainslie, R.J. Decision tablesa tool for tax practitioners. Ttle Tax Adviser 3, 6 (June 1972), 336-345.
• 9: 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]
• 10: 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

Primary Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.3 Formal Languages
          Subjects: Decision problems

Additional Classification:
  E. Data

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

General Terms:
Algorithms

Keywords:
coding, decision tables, flowcharting, information theory, noiseless channel, sorting