• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Computer Science Logic >Implicit Computational Complexity for Higher Type Functionals
【24h】

Implicit Computational Complexity for Higher Type Functionals

机译：高阶功能的隐式计算复杂度

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

In previous works we argued that second order logic with comprehension restricted to positive formulas can be viewed as the core of Feasible Mathematics. Indeed, the equational programs over strings that are provable in this logic compute precisely the poly-time computable functions. Here we investigate the provable functionals of this logic, and show that they are precisely Cook and Urquhart's basic feasible functionals, BFF. This further confirms the stability of BFF as a notion of computational feasibility in higher type. Using a formula-as-type morphism, we also show that BFF consists precisely of the functionals that are lambda representable in F_2 restricted to positive type arguments (and trivially augmented with basic constructors and destructors).
机译：在以前的著作中，我们认为具有理解力的二阶逻辑仅限于正公式，可以视为可行数学的核心。实际上，在此逻辑中可证明的字符串方程式程序可以精确地计算可乘函数。在这里，我们研究了该逻辑的可证明的功能，并证明它们恰好是Cook和Urquhart的基本可行功能BFF。这进一步证实了BFF的稳定性，这是高级类型中计算可行性的概念。使用按类型表示的态射态，我们还显示BFF精确地由Lambda可在F_2中表示的函数组成，这些函数限于正类型自变量（并使用基本构造函数和析构函数进行了微不足道的扩充）。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号