Summary
For Boolean functions whose variables appear in secondary storage, algorithms which minimize the expected cost of evaluation are considered. An easyto-implement algorithm which gives nearly optimal results is proposed for the case of monotonic functions without a priori probabilities. Optimality proofs are given for a simple special cases.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Gries, D.: Compiler construction for digital computers. New York-London: J. Wiley& Sons 1971
Slage, J. R.: An efficient algorithm for finding certain minimum-cost procedures for making binary decisions. J. ACM 11, 253–264 (1964)
Reinwald, L. T., Soland, R. M.: Conversion of limited entry decision tables to optimal computer programs I: Minimum average processing time. J. ACM 13, 339–358 (1966)
Ganapathy, S., Rajaraman, V.: Information theory applied to the conversion of decision tables to computer programs. Comm. ACM 16, 532–539 (1973)
Breitbart, Y, Reiter, A.: A branch-and-bound algorithm for optimal evaluation of monotonic Boolean functions. Computer Science Dept., Technion Haifa, TR No. 35, April 1974
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Breitbart, Y., Reiter, A. Algorithms for fast evaluation of Boolean expressions. Acta Informatica 4, 107–116 (1975). https://doi.org/10.1007/BF00288743
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF00288743