Combining decision rules in a decision table

ABSTRACT

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 rules implied in the ELSE Rule occur with low frequency, then the ELSE Rule can be used to further simplify the decision table. Several objectives merit consideration in optimizing a decision table: reducing machine execution time; reducing preprocessing time; reducing required machine memory; reducing the number of decision rules. (This often improves the clarity of the decision table to a human reader.) It will be shown that objectives (3) and (4) can be furthered with the above methods. Objective (1) is also attained if overspecified decision rules are not combined. Objective (2) must be compared against the potential benefits of objectives (1), (3), and (4) in deciding whether to use the above methods.

REFERENCES

• 1: Armerding, G.W. FORTAB: A decision table language for scientific computing applications. Rand Corp., RM-3306-PR, Sept. 1962.
• 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: Dixon, P. Decision tables and their application. Computers and Automation 13, 4 (Apr. 1964), 14-19.
• 4: D. L. Fisher, Data, documentation, and decision tables, Communications of the ACM, v.9 n.1, p.26-31, Jan. 1966 [doi>10.1145/365153.365163]
• 5: 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]
• 6: King, P.J.H. Decision tables. The Computer J. 10, 8 (Aug. 1967), 135-142.
• 7: 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]
• 8: McDaniel, H. (Ed.) Decision Table Software. Auerbach, New York, 1970.
• 9: Mendelson, E. Boolean Algebra & Switching Circuits. McGraw-Hill, New York, 1970.
• 10: Pollack, S.L. How to build and analyze decision tables. Rand Corp. Memo, P-2829, Nov. 1963.
• 11: Pollack, S.L. CODASYL, COBOL and DETAB-X, Datamation 9, 2 (Feb. 1963), 61.
• 12: 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]
• 13: Pollack, S.L., Hicks, H.T., Jr., and Harrison, W.J., Decision Tables: Theory and Practice. Wiley, New York, 1971.
• 14: Solomon L. Pollack, Comment on the conversion of decision tables to computer programs, Communications of the ACM, v.14 n.1, p.52, Jan. 1971 [doi>10.1145/362452.362514]
• 15: Prather, R.E. Introduction to Switching Theory: A Mathematical Approach. Allyn and Bacon, Boston, 1967.
• 16: 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]
• 17: 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]
• 18: Schmidt, D.T., and Kavanagh, T.F. Using decision structure tables. Datamation, 10, (Feb.-Mar. 1964).
• 19: Schubert, E.J. The relative merits of minimization techniques for switching circuits. IEEE-EC-12 (1963), 321-322.
• 20: 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]
• 21: Cyril G. Veinott, Programming decision tables in FORTRAN, COBOL or ALGOL, Communications of the ACM, v.9 n.1, p.31-35, Jan. 1966 [doi>10.1145/365153.365164]
• 22: 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:
  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS
      H.4.2 Types of Systems
          Subjects: Decision support (e.g., MIS)

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN

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

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Management

Keywords:
boolean method, coding, decision tables, flowcharting, logic circuit, maximization, minimization, prime implicant, sorting, the Quine-McCluskey method