Tagged BDDs: Combining reduction rules from different decision diagram types
Tagged BDDs: Combining reduction rules from different decision diagram types
复制标题
标记 BDD：组合来自不同决策图类型的约简规则
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
R. Meolic
中科院分区：
文献类型：
--
作者：
T. V. Dijk;R. Wille;R. Meolic
二元决策图是离散数学、电子工程和计算机科学中的基本数据结构。二元决策图存在许多不同的变体，特别是采用不同归约规则的变体。对于某些应用，例如动态状态空间探索，多个约简规则有利于最小化所涉及的图的大小。我们提出了标记的二元决策图，一个基于边的方法，允许同时使用两个约简规则。实验评估表明，在飞行状态空间探索是一个数量级更快地使用标记的二元决策图相比，传统的二元决策图。
Binary decision diagrams are fundamental data structures in discrete mathematics, electrical engineering and computer science. Many different variations of binary decision diagrams exist, in particular variations that employ different reduction rules. For some applications, such as on-the-fly state space exploration, multiple reduction rules are beneficial to minimize the size of the involved graphs. We propose tagged binary decision diagrams, an edge-based approach that allows to use two reduction rules simultaneously. Experimental evaluations demonstrate that on-the-fly state space exploration is an order of magnitude faster using tagged binary decision diagrams compared to traditional binary decision diagrams.