For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Relationships between Horn Formulas and XOR-MDNF Formulas
Kenshi MATSUO Tetsuya KOYAMA Eiji TAKIMOTO Akira MARUOKA
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2004/02/01
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.