Coudert, Olivier Two-level logic minimization: An overview. (English) Zbl 0818.94025 Integr., VLSI J. 17, No. 2, 97-140 (1994). Summary: Forty years ago, W. V. Quine [Am. Math. Mon. 59, 521-531 (1952; Zbl 0048.245)] noted that finding a procedure that computes a minimal sum of products for a given propositional formula is very complex, even though propositional formulas are fairly simple. Since this early work, this problem, known as two-level logic minimization, has attracted much attention. It arises in several fields of computer science, e.g., in logic synthesis, reliability analysis, and automated reasoning. This paper exposes the classical approach for two-level logic minimization, and presents the recent developments that overcome the limitations of the procedures proposed in the past. We show that these new techniques yield a minimizer that is from 10 up to 50 times faster than the previously best known ones, and that is able to handle more complex functions. Cited in 10 Documents MSC: 94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010) 03B05 Classical propositional logic 68W10 Parallel algorithms in computer science Keywords:set covering problem; binary decision diagram; combinational set; propositional formula; two-level logic minimization; logic minimization Citations:Zbl 0048.245 PDFBibTeX XMLCite \textit{O. Coudert}, Integr., VLSI J. 17, No. 2, 97--140 (1994; Zbl 0818.94025) Full Text: DOI