Efficient Ordering of Set Expressions for Symbolic Expansion

ABSTRACT

This paper gives an algorithm for efficiently ordering the terms and factors of a set (or Boolean) expression so that the work required for the symbolic expansion of the expression according to the distributive law is minimized. Formulas are given for computing the measure of work associated with any ordering of an expression. It is shown from these formulas that reordering the factors of the intersections can possibly reduce the cost of expansion, but this cost is invariant with respect to the ordering of the terms of the unions. A simple ordering algorithm is given for quickly determining an optimal (not necessarily unique) ordering of an intersection and a union. When this algorithm is applied to all intersections and unions in an expression, the resulting order is shown to minimize the total work over all possible orderings. Thus it is easy to establish an optimal ordering for an expression and estimate the machine time for its symbolic expansion before doing the expansion.

REFERENCES

• 1: BIRKHOFF, G, AND BARTEE, T C Moder~ Apphed Algebra. McGraw-Hill, New York, 1970
• 2: Melvin A. Breuer, Heuristic switching expression simplification, Proceedings of the 1968 23rd ACM national conference, p.241-250, August 27-29, 1968 [doi>10.1145/800186.810584]
• 3: I~{cCLUSKEY, E. J Ja Mlmm~zatlon of Boolean functions Bell System Tech. J 85 (1956), 1417- 1444.
• 4: QUINE, W. V The problem of mmplffying truth functions Amer. Math Monthly 59 (1952), 521-531.
• 5: QUINE, W. V A way to simphfy truth functions. Amer. Math. Monthly 62 (1955), 627-631.
• 6: WHITESITW, J E Boolean Algebra and Its Apphcat~ons Addison-Wesley, Reading, Mass., 1961.
• 7: WORanLL, R B Set equatlo~ transformation system (SETS). SLA-73-0028, Sandla Laboratories, Albuquerque, N Mex, June 1973.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

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