Relationships between Horn Formulas and XOR-MDNF Formulas

Kenshi Matsuo, Tetsuya Koyama, Eiji Takimoto, Akira Maruoka

Research output: Contribution to journalArticlepeer-review


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 = f1⊗ ⋯ ⊗ fd, 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 f̄ 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.

Original languageEnglish
Pages (from-to)343-351
Number of pages9
JournalIEICE Transactions on Information and Systems
Issue number2
Publication statusPublished - Feb 2004
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Hardware and Architecture
  • Computer Vision and Pattern Recognition
  • Electrical and Electronic Engineering
  • Artificial Intelligence


Dive into the research topics of 'Relationships between Horn Formulas and XOR-MDNF Formulas'. Together they form a unique fingerprint.

Cite this