An ordered binary decision diagram (OBDD) is a graph representation of a Boolean function. In this paper, the size of ordered binary decision diagrams representing threshold functions is discussed. We consider two cases: the case when a variable ordering is given and the case when it is adaptively chosen. We show 1) O(2(n/2)) upper bound for both cases, 2) Omega(2(n/2)) lower bound for the former case and 3) Omega(n2(root n/2)) lower bound for the latter case. We also show some relations between the variable ordering and the size of OBDDs representing threshold functions. [References: 16]
展开▼
机译：有序二进制决策图（OBDD）是布尔函数的图形表示。在本文中，讨论了代表阈值函数的有序二元决策图的大小。我们考虑两种情况：给出变量排序的情况和自适应选择的情况。我们显示1）两种情况的O（2（n / 2））上限，2）前一种情况的Omega（2（n / 2））下限和3）Omega（n2（root n / 2））下限必然会发生后一种情况。我们还显示了变量排序和代表阈值函数的OBDD大小之间的一些关系。 [参考：16]
展开▼
