• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Programming languages and systems >Elementary Linear Logic Revisited for Polynomial Time and an Exponential Time Hierarchy
【24h】

Elementary Linear Logic Revisited for Polynomial Time and an Exponential Time Hierarchy

机译：再谈多项式时间和指数时间层次的基本线性逻辑

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

摘要

Elementary linear logic is a simple variant of linear logic, introduced by Girard and which characterizes in the proofs-as-programs approach the class of elementary functions, that is to say computable in time bounded by a tower of exponentials of fixed height. Our goal here is to show that despite its simplicity, elementary linear logic can nevertheless be used as a common framework to characterize the different levels of a hierarchy of deterministic time complexity classes, within elementary time. We consider a variant of this logic with type fix-points and weakening. By selecting specific types we then characterize the class P of polynomial time predicates and more generally the hierarchy of classes k-EXP, for k ≥ 0, where k-EXP is the union of DTIME(2_k~n~i), for i ≥ 1.
机译：基本线性逻辑是线性逻辑的一种简单变体，由Girard引入，其特征是在程序证明中逼近基本函数的类别，也就是说，可以在固定高度的指数塔的范围内进行时间计算。我们的目标是表明，尽管简单，基本线性逻辑仍可以用作通用框架，以描述基本时间内确定性时间复杂度类的层次结构的不同级别。我们考虑这种逻辑的变体，它具有类型固定点和弱化类型。通过选择特定的类型，我们然后表征多项式时间谓词的类P，并且更普遍地描述k-EXP类的层次，对于k≥0，其中k-EXP是DTIME（2_k〜n〜i）的并集，对于i≥ 1。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号