NPN-Representatives of a Set of Optimal Boolean Formulas

• FUKUHARA Hideaki

  Graduate School of Information Sciences, Tohoku University

• TAKIMOTO Eiji

  Department of Informatics, Kyushu University

• AMANO Kazuyuki

  Department of Computer Science, Gunma University

Abstract

For an arbitrary set B of Boolean functions satisfying a certain condition, we give a general method of constructing a class C_B of read-once Boolean formulas over the basis B that has the following property: For any F in C_B, 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 C_B^* so that the set of canonical form formulas consists of only NPN-representatives in C_B^*.

Journal

• IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

  IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E93-A (6), 1008-1015, 2010

  The Institute of Electronics, Information and Communication Engineers

Keywords

• formula complexity
• quantum adversary methods
• NPN-equivalence classes

Details

• CRID: 1390282681287688448
• NII Article ID: 10026864513
• NII Book ID: AA10826239
• DOI: 10.1587/transfun.e93.a.1008
• ISSN: 17451337
• ISSN: 09168508
• Web Site: http://www.jstage.jst.go.jp/article/transfun/E93.A/6/E93.A_6_1008/_pdf
• Text Lang: en
• Data Source:
  • JaLC
  • Crossref
  • CiNii Articles
  • KAKEN
• Abstract License Flag: Disallowed