Relationships between Horn Formulas and XOR-MDNF Formulas


IEICE TRANSACTIONS on Information and Systems   Vol.E87-D   No.2   pp.343-351
Publication Date: 2004/02/01
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science)
XOR-MDNF formula,  monotone DNF formula,  Horn DNF formula,  decision lists,  incrementally polynomial time,  

Full Text: PDF(311.9KB)
>>Buy this Article

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 MDNF formula f is a Boolean formula represented by f = f1fd , where f1 > > fd 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 can be represented by Horn DNF formulas, coincides with a subclass of MDNF formulas such that each DNF formula fi consists of a single term. Furthermore, we give an incrementally polynomial time algorithm that transforms a given Horn DNF formula into the MDNF representation.