二分モーメントグラフによる除算表現の大きさの指数下界

スポンサーリンク

概要

論文の詳細を見る
算術演算回路の設計検証のため提案された二分モーメントグラフは, {0, 1} のベクトルから整数への関数 (f : {0, 1}^n→Z} を表す非巡回有向グラフである. また, マルティプリカティブニ分モーメントグラフは二分モーメントグラフの辺に重みを与えたものである. マルティプリカティブニ分モーメントグラフにおいては, 加算や乗算などの関数を入力の桁数の多項式の大きさの節点数で表現できる. しかし, 除算については節点数の下界が明らかにされていなかった. 本稿では, 二つの2進数の商を与える関数を表すマルティプリカティブ二分モーメントグラフの節点数の下界が指数関数になることを示す.
社団法人電子情報通信学会の論文
1997-10-31

著者

関連論文

もっと見る

スポンサーリンク