Doing two-level logic minimization 100 times faster. (English) Zbl 0858.94035
Clarkson, K. (ed.), Proceedings of the 6th annual ACM-SIAM symposium on discrete algorithms, San Francisco, CA, USA, January 22-24, 1995. Philadelphia, PA: SIAM. 112-121 (1995).
Two-level minimization consists in finding a minimal cost sum-of-products i.e., disjunctive normal form, of a given Boolean function. This paper presents a new algorithm to solve this problem, and gives experimental evidences showing that it outperforms the leading minimizers of several orders of magnitude. It is suspected that it may be possible to explain this improvement in performance theoretically, and will stimulate further research.
For the entire collection see [Zbl 0841.00019].
For the entire collection see [Zbl 0841.00019].
Reviewer: U.Schöning (Ulm)
MSC:
| 94C10 | Switching theory, application of Boolean algebra; Boolean functions (MSC2010) |
| 68Q25 | Analysis of algorithms and problem complexity |
| 03B35 | Mechanization of proofs and logical operations |
