Zero-Suppression and Computation Models
Zero-Suppression and Computation Models
复制标题
零抑制和计算模型
DOI：
10.1007/978-3-319-94667-2_22
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Hiroki Morizumi
中科院分区：
文献类型：
--
作者：
Hiroki Morizumi
零抑制二元决策图（Zero-supplied binary decision diagrams，ZDD）是一种表示布尔函数的数据结构，也是二元决策图（binary decision diagrams，BDD）最成功的变体之一。另一方面，BDD在计算复杂性理论中也被称为分支程序，并且已经作为计算模型进行了研究。在本文中，我们考虑ZDD从计算复杂性理论的观点。首先，我们定义了零抑制分支程序，它实际上与（无序）ZDD具有相同的定义，并考虑零抑制分支程序的计算能力。其次，我们试图推广零抑制的概念。我们称ZDD的基本思想为零抑制。我们证明了零抑制可以应用于其他两个经典的计算模型，决策树和布尔公式。
Zero-suppressed binary decision diagrams (ZDDs) are a data structure representing Boolean functions, and one of the most successful variants of binary decision diagrams (BDDs). On the other hand, BDDs are also called branching programs in computational complexity theory, and have been studied as a computation model. In this paper, we consider ZDDs from the viewpoint of computational complexity theory. Firstly, we define zero-suppressed branching programs, which actually have the same definition to (unordered) ZDDs, and consider the computational power of zero-suppressed branching programs. Secondly, we attempt to generalize the concept of zero-suppression. We call the basic idea of ZDDs zero-suppression. We show that zero-suppression can be applied to other two classical computation models, decision trees and Boolean formulas.