Relationships between Horn Formulas and XOR-MDNF Formulas

• MATSUO Kenshi

  Graduate School of Information Sciences, Tohoku University

• KOYAMA Tetsuya

  Graduate School of Information Sciences, Tohoku University

• TAKIMOTO Eiji

  Graduate School of Information Sciences, Tohoku University

• MARUOKA Akira

  Graduate School of Information Sciences, Tohoku University

Abstract

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 = f_1 ⊕・・・⊕f_d, where f_1 > ・・・ > f_d 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 f_i consists of a single term. Furthermore, we give an incrementally polynomial time algorithm that transforms a given Horn DNF formula into the ⊕MDNF representation.

Journal

• IEICE Transactions on Information and Systems

  IEICE Transactions on Information and Systems 87 (2), 343-351, 2004-02-01

  The Institute of Electronics, Information and Communication Engineers

Keywords

• XOR-MDNF formula
• monotone DNF formula
• Horn DNF formula
• decision lists
• incrementally polynomial time

Details

• CRID: 1570854177341044224
• NII Article ID: 110003223355
• NII Book ID: AA10826272
• ISSN: 09168532
• Text Lang: en
• Data Source:
  • CiNii Articles