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

DOI10.1016/S0890-5401(03)00009-9MaRDI QIDQ1401943zbMATH OpenOpenAlexFDO

Authors Martin Hofmann

Publication date 19 August 2003

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

Full work available at URL https://doi.org/10.1016/s0890-5401(03)00009-9

zbMATH Keywords

Complexity theoryHigher-order functionLinear typesResourcesType system

Mathematics Subject Classification ID

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

Recommendations

• Higher type recursion, ramification and polynomial time
• An arithmetic for non-size-increasing polynomial-time computation
• scientific article; zbMATH DE number 1531370
• A polytime functional language from light linear logic
• Combining linear logic and size types for implicit complexity

Cites work

• A new recursion-theoretic characterization of the polytime functions
• A syntactical analysis of non-size-increasing polynomial time computation
• scientific article; zbMATH DE number 1538025 (Why is no real title available?)
• Light linear logic
• Region-based memory management
• 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

Cited in

(44)

• Light types for polynomial time computation in lambda calculus
• Implicit characterizations of FPTIME and NC revisited
• An arithmetic for non-size-increasing polynomial-time computation
• 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
• Polynomial time over the reals with parsimony
• Algorithmically broad languages for polynomial time and space
• A type-assignment of linear erasure and duplication
• Types for complexity of parallel computation in pi-calculus
• 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
• Linear dependent types in a call-by-value scenario
• Higher-order interpretations and program complexity
• Bounded combinatory logic and lower complexity
• 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
• Objects in polynomial time
• Polynomial Size Analysis of First-Order Functions
• Polynomial Size Analysis of First-Order Shapely Functions
• Some Complexity and Expressiveness Results on Multimodal and Stratified Proof Nets
• Safe recursion revisited. I: Categorical semantics for lower complexity
• scientific article; zbMATH DE number 2006627 (Why is no real title available?)
• scientific article; zbMATH DE number 1531370 (Why is no real title available?)
• scientific article; zbMATH DE number 1834639 (Why is no real title available?)
• Combining linear logic and size types for implicit complexity
• Pointers in recursion: exploring the tropics
• Linear sized types in the calculus of constructions
• Proof-theoretic semantics and feasibility
• Non-linearity as the metric completion of linearity
• Realizability models and implicit complexity
• Computer Science Logic
• A syntactical analysis of non-size-increasing polynomial time computation
• Two decades of automatic amortized resource analysis
• Implicit computation complexity in higher-order programming languages
• Bounded Linear Logic, Revisited
• A characterization of basic feasible functionals through higher-order rewriting and tuple interpretations
• Two algorithms in search of a type-system
• Unbounded recursion and non-size-increasing functions
• Gödel's system T revisited

This page was built for publication: Linear types and non-size-increasing polynomial time computation.

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