AN APPLICATION OF CATEGORY-THEORETIC SEMANTICS TO THE CHARACTERISATION OF COMPLEXITY CLASSES USING HIGHER-ORDER FUNCTION ALGEBRAS

Martin Hofmann

首页> 外文期刊>The bulletin of symbolic logic >AN APPLICATION OF CATEGORY-THEORETIC SEMANTICS TO THE CHARACTERISATION OF COMPLEXITY CLASSES USING HIGHER-ORDER FUNCTION ALGEBRAS

【24h】

AN APPLICATION OF CATEGORY-THEORETIC SEMANTICS TO THE CHARACTERISATION OF COMPLEXITY CLASSES USING HIGHER-ORDER FUNCTION ALGEBRAS

机译：分类理论语义学在高阶函数代数刻画复杂性分类中的应用

获取原文

获取原文并翻译 | 示例

掌桥外文数据库（机构版） >>

开具论文收录证明 >>

文献代查 >>

页面导航

摘要
著录项
相似文献
相关主题

摘要

We use the category of presheaves over PTIME-functions in order to show that Cook and Urquharl's higher-order function algebra PV' defines exactly the PTIME-fimctions. As a byproduct we obtain a syntax-free generalisation of FTMtfi'-compuiabilily to higher types. By restricting to sheuves for a suitable topology we obtain a model for intuilionistic pred?icate logic with ∑ fom 1 to b of-induction over PVU and use this to re-establish thai the p'rovably total functions in this system are polynomial time computable. Finally, we apply the category-theoretic approach to a new higher-order extension of Bellantoni-Cook's system BC of safe recursion.

机译：为了说明Cook和Urquharl的高阶函数代数PV'准确地定义了PTIME函数，我们使用了比PTIME函数更早的滑轮。作为副产品，我们可以自由地将FTMtfi'推广到更高类型的语法。通过限制适用于适当拓扑的拓扑，我们获得了直觉性谓词逻辑的模型，其中∑ fom为PVU的归纳为b的归纳法，并以此重新建立该系统中可证明的总函数为多项式时间可计算的。最后，我们将类别理论方法应用于Bellantoni-Cook安全递归系统BC的新的高阶扩展。

著录项

来源
《The bulletin of symbolic logic》 |1997年第4期|共18页
作者
Martin Hofmann;
展开▼
作者单位

展开▼
收录信息
原文格式 PDF
正文语种 eng
中图分类数理逻辑（符号逻辑）;
关键词

相似文献

外文文献
中文文献
专利

1. AN APPLICATION OF CATEGORY-THEORETIC SEMANTICS TO THE CHARACTERISATION OF COMPLEXITY CLASSES USING HIGHER-ORDER FUNCTION ALGEBRAS [J] . Martin Hofmann The bulletin of symbolic logic . 1997,第4期

机译：分类理论语义学在高阶函数代数刻画复杂性分类中的应用
2. Complexity of systems of functions of Boolean algebra and systems of functions of three-valued logic in classes of polarized polynomial forms [J] . Svetlana N. Selezneva Discrete mathematics and applications . 2016,第2期

机译：极化多项式形式的布尔代数函数系统和三值逻辑函数系统的复杂性
3. Algebraic Characterizations of Complexity-Theoretic Classes of Real Functions [J] . Olivier Bournez, Walid Gomaa, Emmanuel Hainry International journal of unconventional computing . 2011,第5期

机译：复杂度的代数表征-实函数的理论类
4. The Power of Non-determinism in Higher-Order Implicit Complexity Characterising Complexity Classes Using Non-deterministic Cons-Free Programming [C] . Cynthia Kop, Jakob Grue Simonsen European symposium on programming;European joint conferences on theory and practice of software . 2017

机译：高阶隐式复杂性中非确定性的力量-使用非确定性的无约束程序来表征复杂性类
5. Topological and category-theoretic aspects of abstract elementary classes. [D] . Lieberman, Michael Joseph. 2009

机译：抽象基本类的拓扑和类别理论方面。
6. Algebraic and Combinatorial Properties of Common RNA Pseudoknot Classes with Applications [O] . Markus E. Nebel, Frank Weinberg -1

机译：常见RNA假结类的代数和组合性质及其应用
7. An Application of Category-Theoretic Semantics to the Characterisation of Complexity Classes Using Higher-Order Function Algebras [O] . Martin Hofmann, Martin Hofmann Darmstadt 1997

机译：类别理论语义在高阶函数代数复杂类表征中的应用
8. An Analysis of Some Relationships Between Post and Boolean Algebras with Application to the Minimization of Higher-Order Boolean Functions [R] . Wojcik, A. S., Metze, G. 1971

机译：一类布尔代数与布尔代数的关系分析及其在高阶布尔函数最小化中的应用

AN APPLICATION OF CATEGORY-THEORETIC SEMANTICS TO THE CHARACTERISATION OF COMPLEXITY CLASSES USING HIGHER-ORDER FUNCTION ALGEBRAS

摘要

著录项

相似文献

相关主题

期刊订阅