An Application of Category-Theoretic Semantics to the Characterisation of Complexity Classes Using Higher-Order Function Algebras

DOI10.2307/421100MaRDI QIDQ4382502zbMATH OpenOpenAlexFDO

Authors Martin Hofmann

Publication date 28 February 2000

Published in The Bulletin of Symbolic Logic (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/07c6705c9d818bad9c6927aa4ddddce1c44839a0, http://www.math.ucla.edu/~asl/bsl/0304-toc.htm

zbMATH Keywords

category of presheaves over PTIME-functionscomputable functionsgeneralisation of PTIME-computability to higher typeshigher-order function algebraintuitionistic predicate logicpolynomial timeprovably total functionssafe recursion

Mathematics Subject Classification ID

Combinatory logic and lambda calculus (03B40) Complexity of computation (including implicit computational complexity) (03D15) Higher-type and set recursion theory (03D65) Categorical logic, topoi (03G30) Presheaves and sheaves, stacks, descent conditions (category-theoretic aspects) (18F20) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Timed Sets, Functional Complexity, and Computability
• Game semantics approach to higher-order complexity
• scientific article; zbMATH DE number 65741
• A note on complexity measures for inductive classes in constructive type theory

Cites work

• A new recursion-theoretic characterization of the polytime functions
• Functional interpretations of feasibly constructive arithmetic
• scientific article; zbMATH DE number 3959364 (Why is no real title available?)
• Logical relations and the typed λ-calculus
• Provably total functions of intuitionistic bounded arithmetic

Cited in

(9)

• Some fundamental algebraic tools for the semantics of computation. III: Indexed categories
• Safe recursion with higher types and BCK-algebra
• Game semantics approach to higher-order complexity
• The complexity space of partial functions: a connection between complexity analysis and denotational semantics
• A categorical setting for lower complexity
• A categorical framework for congruence of applicative bisimilarity in higher-order languages
• V-comprehensions and P space
• Implicit computation complexity in higher-order programming languages
• Primitive recursive dependent type theory

This page was built for publication: An Application of Category-Theoretic Semantics to the Characterisation of Complexity Classes Using Higher-Order Function Algebras

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4382502)