TCS-TR-A-05-3

Date: Tue May 17 19:13:38 2005

Title: VSOP (Valued-Sum-Of-Products) Calculator Based on Zero-Suppressed BDDs

Authors: Shin-ichi Minato

Contact:

First name: Shin-ichi
Last name: Minato
Address: Division of Computer Science, Hokkaido University, North 14, West 9, Sapporo 060-0814, Japan.
Email: minato@ist.hokudai.ac.jp

Abstract. Recently, Binary Decision Diagrams (BDDs) are widely used for efficiently manipulating large-scale Boolean function data. BDDs are also applied for handling combinatorial item set 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 {\em VSOP} program developed for calculating combinatorial item set data specified by symbolic expressions based on ZBDD techniques. Our program supports not only combinatorial set operations but also numerical arithmetic operations based on Valued-Sum-Of-Products algebra, such as addition, subtraction, multiplication, division, numerical comparison, etc. We discuss the data structures and algorithms in our program, and show some typical applications. VSOP calculator will be useful for solving many problems in Computer Science.