Author Search Result

[Author] Kenshi MATSUO(1hit)

1-1hit
  • Relationships between Horn Formulas and XOR-MDNF Formulas

    Kenshi MATSUO  Tetsuya KOYAMA  Eiji TAKIMOTO  Akira MARUOKA  

     
    PAPER

      Vol:
    E87-D No:2
      Page(s):
    343-351

    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.

FlyerIEICE has prepared a flyer regarding multilingual services. Please use the one in your native language.