Relationships between Horn Formulas and XOR-MDNF Formulas(<Special Section>Foundations of Computer Science)

スポンサーリンク

概要

• 論文の詳細を見る

• 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.

• 社団法人電子情報通信学会の論文
• 2004-02-01

著者

• Takimoto Eiji

  Graduate School Of Information Sciences Tohoku University

• Maruoka Akira

  Graduate School Of Information Sciences Tohoku University

• Matsuo Kenshi

  Graduate School Of Information Sciences Tohoku University

• KOYAMA Tetsuya

  Graduate School of Information Sciences, Tohoku University

• Koyama Tetsuya

  Graduate School Of Information Sciences Tohoku University

関連論文

• DS-1-2 On Formula Size Lower Bounds for Synthesis of Boolean Functions over Disjoint Sets of Variables
• An On-Line Prediction Algorithm Combining Several Prediction Strategies in the Shared Bet Model
• Learning k -Term Monotone Boolean Formulae
• Online Allocation with Risk Information(Invited Papers from New Horizons in Computing)
• Relationships between Horn Formulas and XOR-MDNF Formulas(Foundations of Computer Science)
• On the Sample Complexity of Consistent Learning with One-Sided Error
• Proper learning algorithm for functions of $k$ terms under smooth distributions

スポンサーリンク