License: 
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CSL.2012.198
URN: urn:nbn:de:0030-drops-36738
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2012/3673/
Chrzaszcz, Jacek ;
Schubert, Aleksy
ML with PTIME complexity guarantees
Abstract
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.
BibTeX - Entry
@InProceedings{chrzaszcz_et_al:LIPIcs:2012:3673,
author = {Jacek Chrzaszcz and Aleksy Schubert},
title = {{ML with PTIME complexity guarantees}},
booktitle = {Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL},
pages = {198--212},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-42-2},
ISSN = {1868-8969},
year = {2012},
volume = {16},
editor = {Patrick C{\'e}gielski and Arnaud Durand},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2012/3673},
URN = {urn:nbn:de:0030-drops-36738},
doi = {10.4230/LIPIcs.CSL.2012.198},
annote = {Keywords: implicit computational complexity, polymorphism, soft type assignment}
}
|
Keywords: |
|
implicit computational complexity, polymorphism, soft type assignment |
|
Collection: |
|
Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL |
|
Issue Date: |
|
2012 |
|
Date of publication: |
|
03.09.2012 |
