論理式を分離加法形式で表す手法の時間計算量について

DOI 機関リポジトリ Web Site

書誌事項

タイトル別名
  • On the time Complexity of Methods to Derive the Disjoint Disjunctive Form of Logical Expressions
  • ロンリシキ オ ブンリ カホウ ケイシキ デ アラワス シュホウ ノ ジカン

この論文をさがす

説明

type:Article

In this paper, we deal with the time complexty of (our) MA method, (SASAO's) SAS method and (CHAN's) DT method to derive the disjoint disjunctive form of a binary function with p-valued input. The times complexity of MA method is derived directly by estimating the number of trouble expended on each step of the algorithm for one of the function which has the maximum number of terms in the case of n-variables. That of SAS method and DT method which belong to tree type algorithms is derived by enumerating the summation of the number of terms at each node of those trees for the same function. The following time complexities are shown: for MA method, 0 (np^<2n>): both of SAS method and DT method, 0 (n^2p^n).

p値入力2値関数を分離加法形式で表す3つの方法，（我々の）MA法，（笹尾の）SAS法，（CHANの) DT法の時間計算量を求めている。MA法の時間計算量は，n変数の関数で一番項数の多い関数の一つについて，アルゴリズムの各ステップで必要な手数を直接求めて算出している。DT法，SAS法の時間計算量は，これらが木形アルゴリズムなので，同じ関数について各分岐点での項の総数を算出することにより導いている。結果は，MA法ではO(np^2n)，SAS法，DT法ではともにO(n^2p^n)となる。

identifier:富山大学工学部紀要，43, Page 51-62

収録刊行物

キーワード

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

問題の指摘

ページトップへ