• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Journal of logic and computation >KBOs, ordinals, subrecursive hierarchies and all that
【24h】

KBOs, ordinals, subrecursive hierarchies and all that

机译：KBO，常规，子递归层次结构以及所有这些

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

摘要

We study the complexity of term rewrite systems compatible with the Knuth-Bendix order, if the signature of the rewrite system is potentially infinite. We show that the known bounds on the derivation height are essentially preserved, if the rewrite system fulfils some mild conditions. This allows us to obtain bounds on the derivational height of non-simply terminating rewrite systems. As a corollary, we re-establish an essentially optimal 2-recursive upper bound on the derivational complexity of finite rewrite systems compatible with a Knuth-Bendix order. Furthermore, we link our main result to results on generalized Knuth-Bendix orders and to recent results on transfinite Knuth-Bendix orders.
机译：如果重写系统的签名可能是无限的，我们将研究与Knuth-Bendix顺序兼容的术语重写系统的复杂性。我们表明，如果重写系统满足某些温和条件，则可以保留导数高度上的已知范围。这使我们能够获得非简单终止重写系统的派生高度的界限。因此，我们在与Knuth-Bendix阶数兼容的有限重写系统的导数复杂度上，重新建立了一个本质上最优的2递归上限。此外，我们将主要结果链接到广义Knuth-Bendix订单的结果以及最近的超限Knuth-Bendix订单的结果。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号