Cost recurrences for DML programs
A cost recurrence describes an upper bound for the running time of a program in terms of the size of its input. Finding cost recurrences is a frequent intermediate step in complexity analysis, and this step requires an abstraction from data to data size. In this article, we use information contained...
Published in: | ACM SIGPLAN Notices |
---|---|
Main Author: | |
Format: | Article in Journal/Newspaper |
Language: | English |
Published: |
Association for Computing Machinery (ACM)
2001
|
Subjects: | |
Online Access: | http://dx.doi.org/10.1145/507669.507666 https://dl.acm.org/doi/pdf/10.1145/507669.507666 |
id |
cracm:10.1145/507669.507666 |
---|---|
record_format |
openpolar |
spelling |
cracm:10.1145/507669.507666 2024-05-19T07:39:26+00:00 Cost recurrences for DML programs Grobauer, Bernd 2001 http://dx.doi.org/10.1145/507669.507666 https://dl.acm.org/doi/pdf/10.1145/507669.507666 en eng Association for Computing Machinery (ACM) ACM SIGPLAN Notices volume 36, issue 10, page 253-264 ISSN 0362-1340 1558-1160 journal-article 2001 cracm https://doi.org/10.1145/507669.507666 2024-05-01T06:46:58Z A cost recurrence describes an upper bound for the running time of a program in terms of the size of its input. Finding cost recurrences is a frequent intermediate step in complexity analysis, and this step requires an abstraction from data to data size. In this article, we use information contained in dependent types to achieve such an abstraction: Dependent ML (DML), a conservative extension of ML, provides dependent types that can be used to associate data with size information, thus describing a possible abstraction. We automatically extract cost recurrences from first-order DML programs, guiding the abstraction from data to data size with information contained in DML type derivations. Article in Journal/Newspaper DML ACM Publications (Association for Computing Machinery) ACM SIGPLAN Notices 36 10 253 264 |
institution |
Open Polar |
collection |
ACM Publications (Association for Computing Machinery) |
op_collection_id |
cracm |
language |
English |
description |
A cost recurrence describes an upper bound for the running time of a program in terms of the size of its input. Finding cost recurrences is a frequent intermediate step in complexity analysis, and this step requires an abstraction from data to data size. In this article, we use information contained in dependent types to achieve such an abstraction: Dependent ML (DML), a conservative extension of ML, provides dependent types that can be used to associate data with size information, thus describing a possible abstraction. We automatically extract cost recurrences from first-order DML programs, guiding the abstraction from data to data size with information contained in DML type derivations. |
format |
Article in Journal/Newspaper |
author |
Grobauer, Bernd |
spellingShingle |
Grobauer, Bernd Cost recurrences for DML programs |
author_facet |
Grobauer, Bernd |
author_sort |
Grobauer, Bernd |
title |
Cost recurrences for DML programs |
title_short |
Cost recurrences for DML programs |
title_full |
Cost recurrences for DML programs |
title_fullStr |
Cost recurrences for DML programs |
title_full_unstemmed |
Cost recurrences for DML programs |
title_sort |
cost recurrences for dml programs |
publisher |
Association for Computing Machinery (ACM) |
publishDate |
2001 |
url |
http://dx.doi.org/10.1145/507669.507666 https://dl.acm.org/doi/pdf/10.1145/507669.507666 |
genre |
DML |
genre_facet |
DML |
op_source |
ACM SIGPLAN Notices volume 36, issue 10, page 253-264 ISSN 0362-1340 1558-1160 |
op_doi |
https://doi.org/10.1145/507669.507666 |
container_title |
ACM SIGPLAN Notices |
container_volume |
36 |
container_issue |
10 |
container_start_page |
253 |
op_container_end_page |
264 |
_version_ |
1799479022900477952 |