• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Information Processing Letters >A simpler counterexample to a long-standing conjecture on the complexity of Bryant's apply algorithm
【24h】

A simpler counterexample to a long-standing conjecture on the complexity of Bryant's apply algorithm

机译：一个长期以来关于布莱恩特应用算法复杂性的猜想的更简单的反例

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

摘要

In 1986 in his seminal paper Bryant has introduced Ordered Binary Decision Diagrams (OBDDs) as a dynamic data structure for the representation and manipulation of Boolean functions which allow efficient algorithms for important operations like synthesis, the combination of two Boolean functions by a Boolean operator, and equivalence checking. Based on his empirical evaluation he has conjectured that his apply algorithm for the synthesis works in linear time with respect to the input and output size. Recently in 2012, Yoshinaka et al. have presented a counterexample which contradicts this conjecture but their example has the drawback that the chosen variable ordering for the OBDD representation of the input and output is bad. Therefore, they have raised the question whether Bryant's conjecture may still stand for reasonable variable orderings. Here, a negative answer is given by presenting a simple counterexample which works for such kind of variable orderings.
机译：1986年，科比（Bryant）在他的开创性论文中引入了有序二元决策图（OBDDs），作为一种动态数据结构，用于表示和操作布尔函数，从而可以对诸如合成等重要运算进行有效的算法，布尔运算符将两个布尔函数组合在一起，和等效性检查。根据他的经验评估，他推测他的综合应用算法相对于输入和输出大小在线性时间内工作。最近在2012年，Yoshinaka等人。已经提出了与该猜想相矛盾的反例，但是他们的例子具有缺点，即输入和输出的OBDD表示所选择的变量排序不好。因此，他们提出了一个问题，即科比的猜想是否仍然可以代表合理的变量排序。在这里，通过给出一个简单的反例给出否定答案，该反例适用于此类变量排序。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号