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

DOI10.1016/j.ic.2015.12.011zbMath1339.68098OpenAlexW2230975172MaRDI QIDQ276263

Aleksy Schubert, Jacek Chrząszcz

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

undecidabilitypolymorphism\(\lambda\)-calculusimplicit computational complexity

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Lectures on the Curry-Howard isomorphism
• The undecidability of the semi-unification problem
• The typed lambda-calculus is not elementary recursive
• Light linear logic
• Typability and type checking in System F are equivalent and undecidable
• Soft linear logic and polynomial time
• Soft Linear Logic and Polynomial Complexity Classes
• The Role of Polymorphism in the Characterisation of Complexity by Soft Types
• A logical account of pspace
• A Soft Type Assignment System for λ-Calculus
• Type Inference for a Polynomial Lambda Calculus
• Verification of Ptime Reducibility for system F Terms: Type Inference in Dual Light Affine Logic
• On light logics, uniform encodings and polynomial time
• Theoretical Computer Science
• Theoretical Computer Science

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