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

参考文献9件

書誌事項

タイトル別名
  • Size and Variable Ordering of OBDDs Representing Threshold Functions

この論文をさがす

説明

二分決定グラフはグラフによる論理関数の表現法の一つである。二分決定グラフを用いて論理関数を表現する場合、そのサイズが大きくなると記憶量の点から処理が困難になる。そのため、種々の関数を表現するために必要となる二分決定グラフのサイズに関する研究が重要である。本稿では、しきい値関数を表現する二分決定グラフのサイズについて考察する。しきい値関数を表現する二分決定グラフのサイズの下界がΩ(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.

収録刊行物

参考文献 (9)*注記

もっと見る

キーワード

詳細情報 詳細情報について

  • CRID
    1571980077283176192
  • NII論文ID
    110003191450
  • NII書誌ID
    AN10013152
  • 本文言語コード
    en
  • データソース種別
    • CiNii Articles

問題の指摘

ページトップへ