Conversion of Limited-Entry Decision Tables to Optimal Computer Programs II: minimum storage requirement

ABSTRACT

Given the number of words of computer storage required by the individual tests in a limited-entry decision table, it is sometimes desirable to find an equivalent computer program with minimum total storage requirement. In this paper an algorithm is developed to do this. The rules in the decision table are grouped into action sets, so that several rules with the same actions need not be distinguished. Moreover, if certain combinations of conditions can be excluded from consideration, the algorithm will take advantage of this extra information. The algorithm is initially developed for computer programs possessing a treelike form and then extended to a wider class of programs. The algorithm can be combined with one which finds an equivalent computer program with minimum average processing time, and thus used to find an equivalent computer program which minimizes a cost function which is nondecreasing in both average processing time and total storage requirement.

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: 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]
• 3: LITTLE, J. D. C., MURTY, K. G., SWEENEY, D. W., AND KARIB, C. An algorithm for the Traveling Salesman Problem, Oper. Res. 11 (1963), 972-989.
• 4: MONTALBANO, M. Tables, flow charts and program logic. IBM Syst. J . 1 (Sept. 1962), 51-63,
• 5: 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]
• 6: Laurence I. Press, Conversion of decision tables to computer programs, Communications of the ACM, v.8 n.6, p.385-390, June 1965 [doi>10.1145/364955.364989]
• 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]

INDEX TERMS

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

General Terms:
Algorithms, Measurement, Performance, Theory, Verification