ML with PTIME complexity guarantees

DOI10.4230/LIPICS.CSL.2012.198zbMATH Open1252.68063OpenAlexW2247960266MaRDI QIDQ4649547FDOQ4649547

Authors: Jacek Chrząszcz, Aleksy Schubert 

Publication date: 22 November 2012

Full work available at URL: http://www.frontiersinai.com/turingfiles/September/19.pdf

Recommendations

• Polynomial time calculi.
• Foundations of Software Science and Computation Structures
• Polynomial Time in the Parametric Lambda Calculus.
• A type assignment for \(\lambda\)-calculus complete both for FPTIME and strong normalization
• The role of polymorphism in the characterisation of complexity by soft types

zbMATH Keywords

implicit computational complexitypolymorphismsoft type assignment

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Proof-theoretic aspects of linear logic and other substructural logics (03F52) Functional programming and lambda calculus (68N18)

Cited In (3)

• A type assignment for \(\lambda\)-calculus complete both for FPTIME and strong normalization
• The role of polymorphism in the characterisation of complexity by soft types
• The role of polymorphism in the characterisation of complexity by soft types

This page was built for publication: ML with PTIME complexity guarantees

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