The role of polymorphism in the characterisation of complexity by soft types

DOI10.1016/J.IC.2015.12.011MaRDI QIDQ276263zbMATH OpenOpenAlexFDO

Authors Jacek Chrząszcz, Aleksy Schubert

Publication date 3 May 2016

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

Full work available at URL https://doi.org/10.1016/j.ic.2015.12.011

zbMATH Keywords

implicit computational complexity\(\lambda\)-calculuspolymorphismundecidability

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Combinatory logic and lambda calculus (03B40) Proof-theoretic aspects of linear logic and other substructural logics (03F52)

Recommendations

• The role of polymorphism in the characterisation of complexity by soft types
• Type Inference for a Polynomial Lambda Calculus
• A Soft Type Assignment System for λ-Calculus
• Soft linear logic and polynomial complexity classes
• ML with PTIME complexity guarantees

Cites work

• scientific article; zbMATH DE number 1722667 (Why is no real title available?)
• scientific article; zbMATH DE number 3888913 (Why is no real title available?)
• scientific article; zbMATH DE number 4170889 (Why is no real title available?)
• scientific article; zbMATH DE number 1341609 (Why is no real title available?)
• scientific article; zbMATH DE number 512786 (Why is no real title available?)
• scientific article; zbMATH DE number 2079048 (Why is no real title available?)
• scientific article; zbMATH DE number 784042 (Why is no real title available?)
• A Soft Type Assignment System for λ-Calculus
• A logical account of pspace
• Lectures on the Curry-Howard isomorphism
• Light linear logic
• On light logics, uniform encodings and polynomial time
• On the computational complexity of cut-elimination in linear logic.
• Soft linear logic and polynomial complexity classes
• Soft linear logic and polynomial time
• The role of polymorphism in the characterisation of complexity by soft types
• The typed lambda-calculus is not elementary recursive
• The undecidability of the semi-unification problem
• Theoretical Computer Science
• Typability and type checking in System F are equivalent and undecidable
• Type Inference for a Polynomial Lambda Calculus
• Verification of Ptime Reducibility for system F Terms: Type Inference in Dual Light Affine Logic

Cited in

(1)

• The role of polymorphism in the characterisation of complexity by soft types

This page was built for publication: The role of polymorphism in the characterisation of complexity by soft types

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