Thumbnail
Access Restriction
Subscribed

Author Worrell, R. B. ♦ Hulme, B. L.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1973
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
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.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1973-07-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 20
Issue Number 3
Page Count 7
Starting Page 482
Ending Page 488


Open content in new tab

   Open content in new tab
Source: ACM Digital Library