An application of category-theoretic semantics to the characterisation of complexity classes using higher-order function algebras
Graduate studies at Western
Bulletin of Symbolic Logic 3 (4):469-486 (1997)
|Abstract||We use the category of presheaves over PTIME-functions in order to show that Cook and Urquhart's higher-order function algebra PV ω defines exactly the PTIME-functions. As a byproduct we obtain a syntax-free generalisation of PTIME-computability to higher types. By restricting to sheaves for a suitable topology we obtain a model for intuitionistic predicate logic with ∑ 1 b -induction over PV ω and use this to re-establish that the provably 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|
|Keywords||No keywords specified (fix it)|
|Categories||categorize this paper)|
|Through your library||Configure|
Similar books and articles
Steve Awodey & Erich H. Reck, Completeness and Categoricty, Part II: 20th Century Metalogic to 21st Century Semantics.
Stephen Bellantoni & Martin Hofmann (2002). A New "Feasible" Arithmetic. Journal of Symbolic Logic 67 (1):104-116.
Jaap van Oosten (2011). Partial Combinatory Algebras of Functions. Notre Dame Journal of Formal Logic 52 (4):431-448.
S. Awodey & C. Butz (2000). Topological Completeness for Higher-Order Logic. Journal of Symbolic Logic 65 (3):1168-1182.
Tommaso Cortonesi, Enrico Marchioni & Franco Montagna (2010). Quantifier Elimination and Other Model-Theoretic Properties of BL-Algebras. Notre Dame Journal of Formal Logic 52 (4):339-379.
I. Németi & A. Simon (2009). Weakly Higher Order Cylindric Algebras and Finite Axiomatization of the Representables. Studia Logica 91 (1):53 - 62.
Christoph Benzmüller, Chad E. Brown & Michael Kohlhase (2004). Higher-Order Semantics and Extensionality. Journal of Symbolic Logic 69 (4):1027 - 1088.
Erich Grädel & Yuri Gurevich (1995). Tailoring Recursion for Complexity. Journal of Symbolic Logic 60 (3):952-969.
Sorry, there are not enough data points to plot this chart.
Added to index2009-01-28
Total downloads1 ( #292,129 of 739,404 )
Recent downloads (6 months)0
How can I increase my downloads?