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.4KB)

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.