Linear types and non-size-increasing polynomial time computation.

DOI10.1016/S0890-5401(03)00009-9zbMath1054.68065MaRDI QIDQ1401943

Martin Hofmann

Publication date: 19 August 2003

Published in: Information and Computation (Search for Journal in Brave)

zbMATH Keywords

Complexity theory; Resources; Higher-order function; Linear types; Type system

Mathematics Subject Classification ID

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

Related Items

Proof-Theoretic Semantics and Feasibility, Non-linearity as the Metric Completion of Linearity, Bounded Linear Logic, Revisited, Higher-order interpretations and program complexity, Bounded combinatory logic and lower complexity, Safe recursion revisited. I: Categorical semantics for lower complexity, Realizability models and implicit complexity, Two algorithms in search of a type-system, Unbounded recursion and non-size-increasing functions, Gödel's system \(\mathcal T\) revisited, Light types for polynomial time computation in lambda calculus, Implicit characterizations of FPTIME and NC revisited, Stratified coherence spaces: A denotational semantics for light linear logic, Realizability models for BLL-like languages, On an interpretation of safe recursion in light affine logic, Combining linear logic and size types for implicit complexity, On the expressivity of elementary linear logic: characterizing Ptime and an exponential time hierarchy, An abstract approach to stratification in linear logic, Program equivalence in linear contexts, The Power of Closed Reduction Strategies, On quasi-interpretations, blind abstractions and implicit complexity, A Short Introduction to Implicit Computational Complexity, A Categorical Setting for Lower Complexity, Some Complexity and Expressiveness Results on Multimodal and Stratified Proof Nets

Cites Work

• Unnamed Item
• Region-based memory management
• A new recursion-theoretic characterization of the polytime functions
• Light linear logic
• Safe recursion with higher types and BCK-algebra
• Static prediction of heap space usage for first-order functional programs
• The strength of non-size increasing computation
• A syntactical analysis of non-size-increasing polynomial time computation