# Upper and Lower Amortized Cost Bounds of Programs Expressed as Cost Relations

## Abstract

Resource analysis aims at statically obtaining bounds on the resource consumption of programs in terms of input parameters. A well known approach to resource analysis is based on transforming the target program into a set of cost relations, then solving these into a closed-form bound. In this paper we develop a new analysis for computing upper and lower cost bounds of programs expressed as cost relations. The analysis is compositional : it computes the cost of each loop or function separately and composes the obtained expressions to obtain the total cost. Despite being modular, the analysis can obtain precise upper and lower bounds of programs with amortized cost. The key is to obtain bounds that depend on the values of the variables at the beginning and at the end of each program part. In addition we use a novel cost representation called cost structure. It allows to reduce the inference of complex polynomial expressions to a set of linear problems that can be solved efficiently. We implemented our method and performed an extensive experimental evaluation that demonstrates its power.

Item Type: Report 2016 Flores-Montoya, Antonio Upper and Lower Amortized Cost Bounds of Programs Expressed as Cost Relations German Resource analysis aims at statically obtaining bounds on the resource consumption of programs in terms of input parameters. A well known approach to resource analysis is based on transforming the target program into a set of cost relations, then solving these into a closed-form bound. In this paper we develop a new analysis for computing upper and lower cost bounds of programs expressed as cost relations. The analysis is compositional : it computes the cost of each loop or function separately and composes the obtained expressions to obtain the total cost. Despite being modular, the analysis can obtain precise upper and lower bounds of programs with amortized cost. The key is to obtain bounds that depend on the values of the variables at the beginning and at the end of each program part. In addition we use a novel cost representation called cost structure. It allows to reduce the inference of complex polynomial expressions to a set of linear problems that can be solved efficiently. We implemented our method and performed an extensive experimental evaluation that demonstrates its power. Cost analysis, Cost relations, Amortized cost, Lower bounds Zentrale Einrichtungen > University and State Library Darmstadt (ULB)Zentrale Einrichtungen 31 Dec 2016 10:40 TUD-CS-2016-1436 https://download.hrz.tu-darmstadt.de/med... HTML CitationReference ManagerEndNoteSimple MetadataMultiline CSVDublin CoreRDF+XMLASCII CitationT2T_XMLEP3 XMLBibTeXAtomJSONMODS

#### Optionen (nur für Redakteure)

 View Item