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 (circle plusMDNF formulas, for short) and the class of Horn DNF formulas. An circle plusMDNF formula f is a Boolean formula represented by f = f(1) circle plus.... circle plus 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) over bar can be represented by Horn DNF formulas, coincides with a subclass of circle plusMDNF 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 circle plusMDNF representation.
xor-mdnf formula monotone dnf formula horn dnf formula incrementally polynomial time decision lists