NPN-Representatives of a Set of Optimal Boolean Formulas

スポンサーリンク

概要

• 論文の詳細を見る

• For an arbitrary set B of Boolean functions satisfying a certain condition, we give a general method of constructing a class CB of read-once Boolean formulas over the basis B that has the following property: For any F in CB, F can be transformed to an optimal formula (i.e., a simplest formula over the standard basis {AND, OR, NOT}) by replacing each occurrence of a basis function h ∈ B in F with an optimal formula for h. For a particular set of basis functions B* = {AND, OR, NOT, XOR, MUX}, we give a canonical form representation for CB* so that the set of canonical form formulas consists of only NPN-representatives in CB*.

• 2010-06-01

著者

• FUKUHARA Hideaki

  Graduate School of Information Sciences, Tohoku University

• TAKIMOTO Eiji

  Department of Informatics, Kyushu University

• AMANO Kazuyuki

  Department of Computer Science, Gunma University

• Amano Kazuyuki

  Department Of Computer Science Gunma University

• Takimoto Eiji

  Kyushu Univ. Fukuoka‐shi Jpn

• Takimoto Eiji

  Department Of Informatics Kyushu University

• Fukuhara Hideaki

  Graduate School Of Information Sciences Tohoku University

• Fukuhara Hideaki

  Tohoku Univ. Sendai‐shi Jpn

関連論文

• NPN-Representatives of a Set of Optimal Boolean Formulas
• Lower Bounds on Quantum Query Complexity for Read-Once Formulas with XOR and MUX Operators
• Lower Bounds on Quantum Query Complexity for Read-Once Formulas with XOR and MUX Operators
• NPN-Representatives of a Set of Optimal Boolean Formulas
• DS-1-2 On Formula Size Lower Bounds for Synthesis of Boolean Functions over Disjoint Sets of Variables
• Approximate Reduction from AUC Maximization to 1-norm Soft Margin Optimization (情報論的学習理論と機械学習)
• Adaptive Online Prediction Using Weighted Windows
• Approximate Reduction from AUC Maximization to 1-norm Soft Margin Optimization

スポンサーリンク