Please login using the form on menu list.|
It is required to login for Full-Text PDF.
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
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science)
monotone DNF formula,
Horn DNF formula,
incrementally polynomial time,
Full Text: PDF(311.4KB)
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.