Name
Abstract | ||
|---|---|---|
We present a new method for inferring complexity properties for imperative programs with bounded loops. The properties handled are: polynomial (or linear) boundedness of computed values, as a function of the input; and similarly for the running time.It is well known that complexity properties are undecidable for a Turing-complete programming language. Much work in program analysis overcomes this obstacle by relaxing the correctness notion: one does not ask for an algorithm that correctly decides whether the property of interest holds or not, but only for "yes" answers to be sound. In contrast, we reshaped the problem by defining a "core" programming language that is Turing-incomplete, but strong enough to model real programs of interest. For this language, our method is the first to give a certain answer; in other words, our inference is both sound and complete.The essence of the method is that every command is assigned a "complexity certificate", which is a concise specification of dependencies of output values on input. These certificates are produced by inference rules that are compositional and efficiently computable. The approach is inspired by previous work by Niggl and Wunderlich and by Jones and Kristiansen, but use a novel, more expressive kind of certificates. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1007/978-3-540-69407-6_7 | CiE |
Keywords | Field | DocType |
complexity certificate,inferring complexity property,complexity property,complexity inference,bounded loop,programming language,new method,previous work,polynomial time,certain answer,turing-complete programming language,inference rule,static program analysis,program analysis,linear time | PH,Discrete mathematics,Pseudo-polynomial time,Structural complexity theory,Sparse language,Inference,Computer science,Theoretical computer science,Time complexity,Rule of inference,Undecidable problem | Conference |
Volume | ISSN | Citations |
5028 | 0302-9743 | 15 |
PageRank | References | Authors |
0.69 | 6 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Amir M Ben-Amram | 1 | 327 | 30.52 |
| Neil D. Jones | 2 | 2634 | 558.61 |
| Lars Kristiansen | 3 | 24 | 4.65 |