文章基本信息

标题：ML with PTIME complexity guarantees
本地全文：下载
作者：Jacek Chrzaszcz ; Aleksy Schubert
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2012
卷号：16
页码：198-212
DOI：10.4230/LIPIcs.CSL.2012.198
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：Implicit Computational Complexity is a line of research where the possibility to inference a valid property for a program implies that the program runs in particular complexity class. Soft type systems are one of the research threads within the field. We present here a soft type system with ML-like polymorphism that enjoys decidable typechecking, type inference and typability problems and gives polynomial time computational guarantees for the running time of typed programs.
关键词：implicit computational complexity; polymorphism; soft type assignment