文献

J-GLOBAL ID：201302234386290097   整理番号：13A1793868

BDD/ZDDの技術:簡単な歴史と最近の活動

Techniques of BDD/ZDD: Brief History and Recent Activity

著者 (1件)： MINATO Shin-ichi (Graduate School of Information Sci. and Technol., Hokkaido Univ.)
資料名： IEICE Transactions on Information and Systems (Institute of Electronics, Information and Communication Engineers)  (IEICE Transactions on Information and Systems (Institute of Electronics, Information and Communication Engineers))
巻： E96-D  号： 7  ページ： 1419-1429 (J-STAGE)  発行年： 2013年 
JST資料番号： L1371A  ISSN： 0916-8532  資料種別： 逐次刊行物 (A)
記事区分： 解説  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： 離散構造はコンピュータサイエンスと数学のための基礎な材料であり,集合論,記号論理学,帰納法証明,グラフ理論,組合せ論,確率論に関係している。コンピュータで解く多くの問題は代数学処理で離散構造に分解することができる。離散構造を簡潔に表現して,透過性や妥当性の確認,モデルの解析,最適化のようなタスクを効果に実行するのは非常に重要である。最近,BDD(二進決定図)とZDD(ゼロサプレスBDD)に注目が集まっている。なぜなら,いろいろな応用分野の基本的な離散構造である大規模な組合せ論理データを,それらは効果に表現し扱うからである。Bryantの最初のアイデアから四半世紀を経たが,BDDとZDDに関する興味深く興奮させる研究課題が未だにたくさんある。BDD,ZDDはメモリ内データ処理技術に基づいており,ランダムアクセスメモリの恩恵に浴している。最近の汎用PCはギガバイトの主メモリを搭載しており,かつてはメモリ不足で不可能であった大規模問題を今は解くことができる。このように特に2000年以後BDD,ZDD法の適用範囲は広がってきた。この調査報告書はBDD,ZDDに関わる技術の歴史と最近の研究活動について示した。(翻訳著者抄録)

シソーラス用語： *二分決定グラフ ,  構造 ,  代数学 ,  *行動 ,  *技術史 ,  計算機科学 ,  分解
準シソーラス用語： *BDD【グラフ】 ,  コンピュータサイエンス ,  *研究活動 ,  離散構造

分類 (2件)： 論理代数  (JB03000H) ,  グラフ理論基礎  (IA02020S)

引用文献 (50件)：

• [1] R.E. Bryant, “Graph-based algorithms for Boolean function manipulation,” IEEE Trans. Comput., vol.C-35, no.8, pp.677-691, 1986.
• [2] S. Minato, “Zero-suppressed BDDs for set manipulation in combinatorial problems,” Proc. 30th ACM/IEEE Design Automation Conference (DAC'93), pp.272-277, 1993.
• [3] D.E. Knuth, The Art of Computer Programming: Bitwise Tricks & Techniques; Binary Decision Diagrams, Addison-Wesley, 2009.
• [4] E. Loekito, J. Bailey, and J. Pei, “A binary decision diagram based approach for mining frequent subsequences,” Knowledge and Information Systems, vol.24, no.2, pp.235-268, 2010.
• [5] S. Minato, “πDD: A new decision diagram for efficient problem solving in permutation space,” in Theory and Applications of Satisfiability Testing -SAT 2011, ed. K. Sakallah and L. Simon, Lecture Notes in Computer Science, vol.6695, pp.90-104, Springer Berlin Heidelberg, 2011.

タイトルに関連する用語 (4件)： BDD ,  ZDD ,  歴史 ,  活動