"[0545C4F047FE]" . "3"^^ . "I, P(GAP202/10/1188)" . . . . "11320" . "In this short note we introduce a class of Boolean functions de\uFB01ned by a minimum length of its prime implicants. We show that given a DNF one can test in polynomial time whether it represents a function from this class. Moreover, in case that the answer is af\uFB01rmative we present a polynomial time algorithm which outputs a shortest DNF representation of the given function. Therefore the de\uFB01ned class of functions is a new member of a relatively small family of classes for which the Boolean minimization problem can be solved in polynomial time. Finally, we present a generalization of the above class which is still recognizable in polynomial time, and for which the Boolean minimization problem can be approximated within a constant factor." . "In this short note we introduce a class of Boolean functions de\uFB01ned by a minimum length of its prime implicants. We show that given a DNF one can test in polynomial time whether it represents a function from this class. Moreover, in case that the answer is af\uFB01rmative we present a polynomial time algorithm which outputs a shortest DNF representation of the given function. Therefore the de\uFB01ned class of functions is a new member of a relatively small family of classes for which the Boolean minimization problem can be solved in polynomial time. Finally, we present a generalization of the above class which is still recognizable in polynomial time, and for which the Boolean minimization problem can be approximated within a constant factor."@en . "http://www.cs.uic.edu/pub/Isaim2012/WebPreferences/ISAIM2012_Boolean_Cepek_etal.pdf" . . . . . "set cover; consensus method; dnf; boolean minimization"@en . "125382" . "\u010Cepek, Ond\u0159ej" . . . "Boolean functions with long prime implicants"@en . . . . . "Boolean functions with long prime implicants" . "Ku\u0159\u00EDk, Stanislav" . "Ku\u010Dera, Petr" . . "Boolean functions with long prime implicants" . . . . . . "3"^^ . "Boolean functions with long prime implicants"@en . "RIV/00216208:11320/12:10126636!RIV13-GA0-11320___" . "RIV/00216208:11320/12:10126636" . .