Relationships between Horn Formulas and XOR-MDNF Formulas

摘要

We study relationships between the class of Boolean formulas called exclusive-or expansions based on monotone DNF formulas (⊕MDNF formulas, for short) and the class of Horn DNF formulas. An M⊕DNF formula f is a Boolean formula represented by f = f_1⊕···⊕f_d, where f_1 > ···> f_d are monotone DNF formulas and no terms appear more than once. A Horn DNF formula is a DNF formula where each term contains at most one negative literal. We show that the class of double Horn functions, where both f and its negation f can be represented by Horn DNF formulas, coincides with a subclass of ⊕MDNF formulas such that each DNF formula f_i consists of a single term. Furthermore, we give an incrementally polynomial time algorithm that transforms a given Horn DNF formula into the ⊕MDNF representation.