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...
Main Author: | |
---|---|
Other Authors: | |
Format: | Text |
Language: | English |
Published: |
ACM Press
2001
|
Subjects: | |
Online Access: | http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.24.8213 http://www.brics.dk/~grobauer/papers/cost_dml/crec_for_dml.ps.gz |
id |
ftciteseerx:oai:CiteSeerX.psu:10.1.1.24.8213 |
---|---|
record_format |
openpolar |
spelling |
ftciteseerx:oai:CiteSeerX.psu:10.1.1.24.8213 2023-05-15T16:01:09+02:00 Cost Recurrences for DML Programs Bernd Grobauer The Pennsylvania State University CiteSeerX Archives 2001 application/postscript http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.24.8213 http://www.brics.dk/~grobauer/papers/cost_dml/crec_for_dml.ps.gz en eng ACM Press http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.24.8213 http://www.brics.dk/~grobauer/papers/cost_dml/crec_for_dml.ps.gz Metadata may be used without restrictions as long as the oai identifier remains attached to it. http://www.brics.dk/~grobauer/papers/cost_dml/crec_for_dml.ps.gz text 2001 ftciteseerx 2016-01-07T19:09:18Z 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. Text DML Unknown |
institution |
Open Polar |
collection |
Unknown |
op_collection_id |
ftciteseerx |
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. |
author2 |
The Pennsylvania State University CiteSeerX Archives |
format |
Text |
author |
Bernd Grobauer |
spellingShingle |
Bernd Grobauer Cost Recurrences for DML Programs |
author_facet |
Bernd Grobauer |
author_sort |
Bernd Grobauer |
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 |
ACM Press |
publishDate |
2001 |
url |
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.24.8213 http://www.brics.dk/~grobauer/papers/cost_dml/crec_for_dml.ps.gz |
genre |
DML |
genre_facet |
DML |
op_source |
http://www.brics.dk/~grobauer/papers/cost_dml/crec_for_dml.ps.gz |
op_relation |
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.24.8213 http://www.brics.dk/~grobauer/papers/cost_dml/crec_for_dml.ps.gz |
op_rights |
Metadata may be used without restrictions as long as the oai identifier remains attached to it. |
_version_ |
1766397131695849472 |