Superset generation on decision diagrams
Superset generation on decision diagrams
复制标题
决策图上的超集生成
DOI：
10.1007/978-3-319-15612-5_28
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Shin-ichi Minato
中科院分区：
文献类型：
--
作者：
Takahisa Toda;Shogo Takeuchi;Koji Tsuda;Shin-ichi Minato
从给定的集合族生成所有超集很重要，因为它与识别因果关系密切相关。本文提出了一种有效利用压缩数据结构 BDD 和 ZDD 来生成超集的有效方法。我们分析代表所有超集的 BDD 的大小。作为副产品，我们获得了 BDD 大小的一个重要上限，它表示固定变量排序中的单调布尔函数。
Generating all supersets from a given set family is important, because it is closely related to identifying cause-effect relationship. This paper presents an efficient method for superset generation by using the compressed data structures BDDs and ZDDs effectively. We analyze the size of a BDD that represents all supersets. As a by-product, we obtain a non-trivial upper bound for the size of a BDD that represents a monotone Boolean function in a fixed variable ordering.