.png){kind=icon}
返回
.png){kind=icon}
.png){kind=icon}
.png){kind=icon}
.png){kind=icon}
.png){kind=icon}
摘要
En 中文
近年来，循环（或循环）证明受到了越来越多的关注，并被提议作为研究（共）归纳推理的替代设置。特别是，现在已提出了几种基于循环推理的类型系统。然而，关于循环证明的计算复杂性理论方面知之甚少，这些证明展示了复杂的循环结构，这些结构在更常见的“递归方案”中并不典型。本文试图弥合循环证明与隐式计算复杂性（ICC）之间的差距。具体而言，我们基于Bellantoni和Cook著名的safe-normal函数代数引入了一个循环证明系统，并确定了受ICC启发的证明理论约束，以表征多项式时间和初等可计算函数。在此过程中，我们引入了这些类的新递归理论隐式表征，这些表征本身可能具有独立的兴趣。
Keyword:
Cyclic proofs
implicit complexity
function algebras
safe recursion
higher-order complexity
期刊
A
IF:
0
论文数:
18
被引数:
0
机构
引用论文
暂无论文信息