Relationships between Horn Formulas and XOR-MDNF Formulas

Kenshi MATSUO  Tetsuya KOYAMA  Eiji TAKIMOTO  Akira MARUOKA  

Publication
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)
Category: 
Keyword: 
XOR-MDNF formula,  monotone DNF formula,  Horn DNF formula,  decision lists,  incrementally polynomial time,  

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


Summary: 
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.