しきい値関数を表す二分決定グラフのサイズと変数順序

9 References

Bibliographic Information

Other Title
  • Size and Variable Ordering of OBDDs Representing Threshold Functions

Search this article

Description

二分決定グラフはグラフによる論理関数の表現法の一つである。二分決定グラフを用いて論理関数を表現する場合、そのサイズが大きくなると記憶量の点から処理が困難になる。そのため、種々の関数を表現するために必要となる二分決定グラフのサイズに関する研究が重要である。本稿では、しきい値関数を表現する二分決定グラフのサイズについて考察する。しきい値関数を表現する二分決定グラフのサイズの下界がΩ(n2^<cn^<1-ε>>)であることを示す。また、重みの全順序だけを用いたのでは、良い変数順序が得られないことも示す。
An ordered binary decision diagram (OBDD) is a graph representation of a Boolean function. In representing various Boolean functions using OBDDs, the larger the sizes of OBDDs are, the more difficult it is to deal with them because of the memory requirements. Therefore, it is important to investigate the size of OBDDs representing various Boolean functions. In this paper, the size of ordered binary decision diagrams representing threshold functions is discussed. We prove an Ω(n2^<cn^<1-ε>>) lower bound on the OBDD size. We also show that it is not possible to find a good variable ordering only from the total order of weights.

Journal

References(9)*help

See more

Keywords

Details 詳細情報について

  • CRID
    1571980077283176192
  • NII Article ID
    110003191450
  • NII Book ID
    AN10013152
  • Text Lang
    en
  • Data Source
    • CiNii Articles

Report a problem

Back to top