ハッシングの技法を用いた数式処理アルゴリズムとその擬似ブール計画法への応用

概要

論文の詳細を見る
In this paper we propose some algorithms for formula manipulation of Boolean functions and pseudo-Boolean functions. They are based upon the hashing technique. It takes O(m^2) computation time to simplify a (pseudo-) Boolean function using conventional algorithms, where m is the number of terms involved in the function. On the other hand, our algorithms can reduce the computation time to O(m). The performance is attained by two facts. The one is that the size of the hash table is adaptively changed according to the number of terms involved in the function processed, and the other that the test whether a term consists of a single variable or not is made quite easily during the process to hash the term into the table. The performance of the algorithms is checked through some experiments, and also the algorithms are successfully applied to the Pseudo-Boolean Programming algorithm.
一般社団法人情報処理学会の論文
1977-07-15