On the Complexity of Negation-Limited Inverters

  • Tanaka Keisuke
    School of Information Science,Japan Advanced Institute of Science and Technology,Hokuriku
  • Nishino Tetsuro
    School of Information Science,Japan Advanced Institute of Science and Technology,Hokuriku

Bibliographic Information

Other Title
  • 否定数限定反転回路の複雑さについて

Search this article

Description

A negation-limited circuit is a combinational circuit which includes at most log(n+1)NOT gates.We call a negation-limited circuit which inverts n variables an inverter.In this paper,we investigate the complexity of the inverters.For the size of the inverters,we give a new O(n(logn)^2)upper bound as well as a 5n+ 3log(n+1)-6 lower bound.For the depth of the inverters,we give a 4log(n+1)+2 lower bound.Furthermore,we show two superlinear lower bounds on the size of inverters.

Journal

Keywords

Details 詳細情報について

  • CRID
    1570291227422828288
  • NII Article ID
    110003191722
  • NII Book ID
    AN10013152
  • Text Lang
    ja
  • Data Source
    • CiNii Articles

Report a problem

Back to top