ML with PTIME complexity guarantees

DOI10.4230/LIPICS.CSL.2012.198MaRDI QIDQ4649547zbMATH OpenOpenAlexFDO

Authors Jacek Chrząszcz, Aleksy Schubert

Publication date 22 November 2012

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

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)

Recommendations

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

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)