BEM-II: An Arithmetic Boolean Expression Manipulator Using BDDs (Special Section on VLSI Design and CAD Algorithms)
スポンサーリンク
概要
- 論文の詳細を見る
Recently, there has been a lot of research on solving combinatorial problems using Binary Decision Diagrams (BDDs), which are very efficient representations of Boolean functions. We have already developed a Boolean Expression Manipulator, which calculates and reduces Boolean expressions quickly based on BDD techniques. This greatly aids our works on developing VLSI CAD systems and solving combinatorial problems. Any combinatorial problem can be described in Boolean expressions; however, arithmetic operations, such as addition, subtraction, multiplication, equality and inequality, are also used for describing many practical problems. Arithmetic operations provide simple descriptions of problems in many cases. In this paper, we present an arithmetic Boolean expression manipulator (BEM-II), based on BDD techniques. BEM-II calculates Boolean expressions containing arithmetic operations and then displays the results in various formats. It can solve problems represented by a set of equalities and inequalities, which are dealt with using 0-1 linear programming. We show the efficient data structure based on BDD representation, algorithms for manipulating Boolean expressions with arithmetic operations, and good formats for displaying the results. Finally we present the specification of BEM-II and an example of application to the 8-Queens problem. BEM-II is customizable to various applications. It has good computation performance in terms of the total time for programming and execution. We expect BEM-II to be a helpful tool in research and development on digital systems.
- 社団法人電子情報通信学会の論文
- 1993-10-25
著者
-
湊 真一
北海道大学大学院情報科学研究科・科学技術振興機構erato湊離散構造処理系プロジェクト・ /科学技術振興機構erato湊離散構造処理系プロジェクト・北海道大学大学院情報科学研究科
-
Minato Shin-ichi
Ntt Lsi Laboratories
関連論文
- Flexcastによる段階的導入に優れたマルチキャストシステムの設計と実装(ネットワーク・並列分散システムソフトウェア, システム開発論文)
- Flexcastに基づくマルチキャストシステムの開発とその方式設計について(映像通信,コンテンツ配信ネットワーク,マルチキャスト,一般)
- Flexcastによるインターマルチキャスティング方式の提案と日米映像配信実験(映像通信, コンテンツ配信ネットワーク, マルチキャスト, 一般)
- JGNを介した大規模映像配信プラットフォーム(新しいトラヒックモデルと性能評価及び一般)
- B-7-66 リアルタイムストリーム配信における FEC 適用時の課題に関する一考察
- B-7-47 自己組織化多地点配信技術 (Flexcast) を用いた自律広域マルチキャスト法 : (3) 日米間超長距離ネットワークにおける実証実験
- B-7-46 自己組織化多地点配信技術 (Flexcast) を用いた自律広域マルチキャスト法 : (2) 動的アドレスマッピングによるオンデマンド IP マルチキャストトンネリング
- B-7-45 自己組織化多地点配信技術 (Flexcast) を用いた自律広域マルチキャスト法 : (1) Flexcast と IP マルチキャストの連携方式
- BS-5-5 漏洩者の特定と配信停止が可能なマルチキャスト配信方式(BS-5. ネットワークサービスのセキュリティ技術の展開,シンポジウムセッション)
- B-7-4 ネットワークによるフロー切り替えを行うマルチキャスト電子透かし方式の検討(B-7.情報ネットワーク,一般講演)
- B-7-31 トラヒックの平滑化とFECによる講義ノート映像品質の改善(B-7.情報ネットワーク, 通信2)
- Flexcastを用いた講義ノート多地点同報配信システムの検討(ブロードバンドサービス, CDN/P2P/Gridなどのオーバレイネットワーキング技術及び一般)
- FlexcastとJavaAppletに基づくプログラマブルな多地点同報配信アプリケーションの実装法(ブロードバンドサービス, CDN/P2P/Gridなどのオーバレイネットワーキング技術及び一般)
- B-7-73 MulticastVNCを用いた講義ノート配信システムのトラヒック特性評価(B-7. 情報ネットワーク, 通信2)
- 論理合成技術
- BDDの規模によらず一定の実記憶の範囲内で動作するストリーム形式BDD処理アルゴリズム
- BDD(二分決定グラフ)とその応用
- BDDの規模によらず一定の実記憶の範囲内で動作するストリーム形式BDD処理アルゴリズム (デザインガイア'99--システム設計とCAD技術及び一般)
- ゼロサプレス型BDDを用いた系列長制限つき正規表現処理方法
- 48. 道南における胸部 X 線撮影の現況 : 第 4 報 X 線管焦点について(X 線撮影 II, 北海道部会)
- ベイジアンネットワークと離散構造処理系(ベイジアンネットワークの最先端)
- 5.メディア系異分野共同研究プロジェクト(北の国から明日のICTに架ける橋,知の創出を支える次世代IT基盤技術-北海道大学グローバルCOEプログラムと北海道内情報通信系研究グループの活動-)
- D-4-18 高速ストリーム処理のための文字列パターン照合手法とそのFPGA設計(D-4. データ工学,一般セッション)
- D-1-7 並列ビット分配にもとづいた効率的な正規表現照合アルゴリズム(D-1.コンピュテーション,一般セッション)
- BDD/ZDDを用いたペントミノパズルの解の列挙
- 非巡回正規表現に対する効率的なパターン照合
- eラーニングと遠隔FPGAの連携による異分野共同研究環境の開発(ネットワーク,FPGA応用及び一般)
- eラーニングと遠隔FPGAの連携による異分野共同研究環境の開発(ネットワーク,FPGA応用及び一般)
- eラーニングと遠隔FPGAの連携による異分野共同研究環境の開発(ネットワーク,FPGA応用及び一般)
- 命題論理に基づく確率モデルのための二部決定グラフと順序符号化を用いた効率的なEMアルゴリズム(一般講演(構造学習・ベイジアンネット・確率推論),機械学習とその応用)
- 6ZK-10 二分決定グラフを用いた数独パズルの解探索と列挙(情報爆発時代におけるストリームデータと実世界情報処理,学生セッション,「情報爆発」時代に向けた新しいIT基盤技術)
- Double-Decker RFID Tags--Basic Structures and Applications (日韓合同ワークショップ 1st Korea-Japan Joint Workshop on Ubiquitous Computing and Networking Systems (ubiCNS 2005))
- 3ZP-5 ZDDを用いた立体ペントミノパズルの解の列挙(情報爆発時代におけるデータマイニング・アルゴリズム,学生セッション,「情報爆発」時代に向けた新IT基盤技術,情報処理学会創立50周年記念(第72回)全国大会)
- 二分モーメントグラフを用いた大規模多項式の操作手法
- BDDの規模によらず一定の実記憶の範囲内で動作するストリーム形式BDD処理アルゴリズム
- BDDの規模によらず一定の実記憶の範囲内で動作するストリーム形式BDD処理アルゴリズム
- 効率良い正規表現照合のための並列ビット分配にもとづいたハードウェア指向アルゴリズム(アプリケーション2,FPGA応用及び一般)
- 効率良い正規表現照合のための並列ビット分配にもとついたハードウェア指向アルゴリズム(アプリケーション2,FPGA応用及び一般)
- 効率良い正規表現照合のための並列ビット分配にもとづいたハードウェア指向アルゴリズム(アプリケーション2,FPGA応用及び一般)
- 18. 道南における胸部X線撮影の現況 第2報 : 装置の施設間比較 : 北海道部会 : その他
- B-7-108 Virtual BUSにおける資源管理探索機構
- 2.情報爆発時代のための新しい超高速アルゴリズム(パートI:情報爆発時代における新しい基盤技術,情報爆発時代におけるわくわくするITの創出を目指して)
- ゼロサプレス型二分決定グラフを用いたトランザクションデータベースの効率的解析手法(データマイニング,データ工学論文)
- 座長集約 核医学(29〜34)(北海道部会)
- F-024 ベイジアンネットワークを表現するZDDからの高速計算プログラムの自動生成とその評価(F分野:人工知能・ゲーム,一般論文)
- 頻出パターンマイニングのためのゼロサプレス型BDDの変数順序付け方法とその評価(データマイニング,データ工学論文)
- F-011 頻出パタンマイニングのためのゼロサプレス型BDDの変数順序付け方法の高速化の検討(F分野:人工知能・ゲーム)
- F_019 データベース解析のためのゼロサプレス型二分決定グラフの簡単化について(F分野:人工知能・ゲーム)
- データベース解析のためのゼロサプレス型二分決定グラフの簡単化に関する考察 (テーマ:特集「ウェブデータの知的処理」および一般)
- ベイジアンネットワークを表現するZDDからの高速計算プログラムの自動生成 (特集 「知識発見の生命科学への応用」および一般)
- ゼロサプレス型二分決定グラフによる圧縮と知識発見(テーマ,膨大なデータから学ぶもの)
- ゼロサプレス型二分決定グラフによる圧縮と知識発見(テーマ,膨大なデータから学ぶもの)
- F-013 ゼロサプレス型BDDを用いた無順序n-gram表現法の性能評価(F分野:人工知能・ゲーム)
- F-020 コルモゴロフ複雑性に基づく画像圧縮と分類に関する実験と考察(人工知能・ゲーム,一般論文)
- F-012 頻出パタン集合を表現する二分決定グラフの変数順序改善法に関する実験と考察(F分野:人工知能・ゲーム)
- ゼロサプレスBDDによるペトリネットのCTL記号モデル検査
- D-009 ZDDを用いた頻出パタン演算によるWebテキストデータからの知識発見とその評価(D分野:データベース,一般論文)
- F-061 ベイジアンネットワークを表現するZDDの初期変数順序付け方法の改良(人工知能・ゲーム,一般論文)
- D-031 頻出パタン抽出アルゴリズム「LCM over ZDDs」の変数順序付けの影響に関する考察(データベース,一般論文)
- F-050 ベイジアンネットワークを表現するゼロサプレス型BDDの変数順序付けに関する実験と考察(人工知能・ゲーム,一般論文)
- ZDD によるパスの列挙 (計算機科学とアルゴリズムの数理的基礎とその応用)
- 二分決定グラフ(BDD)による命題論理プログラミング
- Symmetric item set mining method using zero-suppressed BDDs and application to biological data (論文特集:データマイニングと統計数理)
- 算術論理式システムBEM-2を使ってパズルを解こう
- ZDDによるベイジアンネットワーク推論の高速化 (特集 「ベイジアン・ネットワークと応用」および一般)
- ベイジアンネットワークを表現するゼロサプレス型BDDの変数順序付け方法に関する考察 (特集 「ベイジアン・ネットワークと応用」および一般)
- Manipulation of Large-Scale Polynomials Using BMDs (Special Section on VLSI Design and CAD Algorithms)
- ZDDを用いたパスの列挙とその性能評価
- D-4-3 共起成分の含意関係に基づく文献データベースからの共著関係の抽出(D-4. データ工学,一般セッション)
- アルゴリズム記述からのBDD生成
- 組合せ回路検証の技術
- 二分決定グラフによる制約充足問題の解法
- ゼロサプレス型BDDを用いた非明示的積和形表現の高速因数分解法
- 2. 計算機上での BDD の処理技法 (<特集> BDD (二分決定グラフ))
- 「わくわく」 - 技術革新のキーワード -
- 共有二分決定グラフの「幅」に着目した変数順序づけ手法
- 「共起成分の含意関係」を満たすアイテム集合のデータマイニング (特集 「人と技術とAI」および一般)
- 組合せ集合の単純直交分解の抽出と発見科学への応用 (テーマ:特集「シンボルグラウンディング問題」および一般)
- πDD:順列集合を演算処理する二分決定グラフ
- 劣モジュラ性を用いた特徴集合列挙(離散系と機械学習,テキスト・Webマイニング,一般)
- DDMF : An Efficient Decision Diagram Structure for Design Verification of Quantum Circuits under a Practical Restriction
- 逆順の系列集合を表すSeqBDDの構築
- 論理関数の共有二分決定グラフによる表現とその効率的処理手法
- 二分決定グラフ(BDD)を活用したデータマイニング・知識発見技術の最近の話題(「自動化:推論,発見,学習,データマイニング」及び一般)
- Fast Generation of Prime-Irredundant Covers from Binary Decision Diagrams
- BEM-II: An Arithmetic Boolean Expression Manipulator Using BDDs (Special Section on VLSI Design and CAD Algorithms)
- Zero-suppressed BDDs and their applications
- Frequent closed item set mining based on zero-suppressed BDDs (論文特集:データマイニングと統計数理)
- Arithmetic Boolean Expression Manipulator Using BDDs
- Streaming BDD manipulation
- データベースの頻出アイテム集合を表すゼロサプレス型BDDの変数順序付けの理論的考察
- VSOP: ゼロサプレス型BDDに基づく「重み付き積和集合」計算プログラム
- 共有二分決定図を用いた論理関数の処理手法について
- 真理値表表現を用いた記号シミュレータ
- AI-1-5 大規模な離散構造データを扱うためのGPU利用法の検討(AI-1.GPUを用いた高速化技術とそのVLSI設計への応用,依頼シンポジウム,ソサイエティ企画)
- BS-1-2 順列集合を操作する効率的なデータ構造とアルゴリズムの研究について(BS-1. 学生による研究室交流会,シンポジウムセッション)
- BS-1-2 順列集合を操作する効率的なデータ構造とアルゴリズムの研究について(BS-1. 学生による研究室交流会,シンポジウムセッション)
- ERATO湊離散構造処理系プロジェクトの概要とシステム設計分野の研究について(FPGA応用)
- 東日本大震災での短縮URLによるサーバ負荷分散とアクセス分析(IPv6ネットワーク,フォトニックネットワーク,新世代・次世代ネットワーク及び一般)
- 高速なパスの列挙アルゴリズムを用いたネットワークの信頼性評価(IPv6ネットワーク,フォトニックネットワーク,新世代・次世代ネットワーク及び一般)