Read/Search this Article
Abstract
二分決定グラフ(BDD)は, 大規模な論理関数データを効率よく表現する技法として広く利用されている.BDDの中でも, ゼロサプレス型BDD(ZBDD)と呼ばれるデータ構造は, 大規模な組合せ集合を非明示的に列挙し効率よく演算処理するのに適しており, 情報科学における様々な問題に適用できる.我々は, 数式により組合せ集合の演算を記述し, これをZBDDを用いて計算するプログラム「VSOP」を開発した.VSOPは単なる組合せ集合演算だけでなく, 集合の各要素に整数値(係数あるいは重み)を定義し, 加減乗除や大小比較等の算術演算を含む数式を処理できることを特長とする.本稿では, VSOPの内部データ構造や演算方法, データ表示形式について述べ, いくつかの応用例を示す.
Recently, Binary Decision Diagrams (BDDs) are widely used for manipulating large-scale Boolean function data. Zero-suppressed BDDs (ZBDDs) are special type of BDDs which are suitable for implicitly handling large-scale combinatorial item set data. In this paper, we present VSOP program developed for calculating combinatorial item set data specified by symbolic expressions based on ZBDD techniques. VSOP supports not only combinatorial set operations but also numerical arithmetic operations based on Valued-Sum-Of-Products algebla, such as addition, subtraction, multiplication, division, numerical comaprison, etc. We discuss the data structures and algorithms in VSOP program, and show some typical applications.
Journal
- IEICE technical report. Theoretical foundations of Computing [List of Volumes]
-
IEICE technical report. Theoretical foundations of Computing 105(72), 31-38, 2005-05-13 [Table of Contents]
The Institute of Electronics, Information and Communication Engineers
