• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Journal of logic and computation >Computing prime implicates by pruning the search space and accelerating subsumption
【24h】

Computing prime implicates by pruning the search space and accelerating subsumption

机译：通过修剪搜索空间并加快归类来计算素数蕴含

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

摘要

The prime implicate trie (pi-trie) of a logical formula is a tree whose branches are labelled with the prime implicates of the formula. An algorithm that builds the pi-trie from a logical formula was introduced in [15]; it builds the trie recursively and makes extensive use of subsumption testing. A more efficient version in which the use of subsumption is reduced is presented in this article. The improved algorithm is illustrated with experiments. The algorithm naturally lends itself to selecting restricted sets-e.g. only positive prime implicates or only those of bounded length, both useful properties for some applications. Such restrictions can provide significant advantages in efficiency since the set of all prime implicates of a logical formula is typically exponential in size.
机译：逻辑公式的素数蕴含特里（pi-trie）是一棵树，其分支用公式的素蕴表示。在[15]中介绍了一种根据逻辑公式构建pi-trie的算法。它以递归方式构建了Trie，并广泛使用了包含测试。本文介绍了一种更有效的版本，其中减少了使用包含。实验证明了改进算法的有效性。该算法自然适用于选择受限集，例如对于某些应用而言，只有正的素数蕴含或有限的长度都有意义。这样的限制可以在效率上提供明显的优势，因为逻辑公式的所有素数集合的大小通常都是指数的。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号