• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>SOFSEM 2009: Theory and practice of computer science >On the OBDD Complexity of Threshold Functions and the Variable Ordering Problem
【24h】

On the OBDD Complexity of Threshold Functions and the Variable Ordering Problem

机译：阈值函数的OBDD复杂度和变量排序问题

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Ordered binary decision diagrams (OBDDs) are one of the most common dynamic data structures for Boolean functions. Among the many areas of application are verification, model checking, computer aided design, relational algebra, and symbolic graph algorithms. Threshold functions are the basic functions for discrete neural networks and are used as building blocks in the design of symbolic graph algorithms. In this paper the first exponential lower bound on the size of a more general model than OBDDs and the first nontrivial asymptotically optimal bound on the OBDD size for a threshold function are presented. Furthermore, if the number of different weights is a constant it is shown that computing an optimal variable order for multiple output threshold functions is NP-hard whereas for single output function the problem is solvable in deterministic polynomial time.
机译：有序二进制决策图（OBDD）是布尔函数最常见的动态数据结构之一。在许多应用领域中，包括验证，模型检查，计算机辅助设计，关系代数和符号图算法。阈值函数是离散神经网络的基本函数，在符号图算法设计中用作构建块。在本文中，提出了比OBDD更通用的模型的大小的第一个指数下界，以及阈值函数的OBDD大小的第一个非平凡渐近最优界限。此外，如果不同权重的数量为常数，则表明为多个输出阈值函数计算最佳可变阶数是NP-hard的，而对于单个输出函数，该问题可以在确定的多项式时间内解决。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号