Abstract
One way to analyse programs is to to derive expressions for
their computational behaviour. A time bound function (or
worst-case complexity) gives an upper bound for the
computation time as a function of the size of input. We
describe a system to derive such time bounds automatically
using abstract interpretation. The semantics-based setting
makes it possible to prove the correctness of the time bound
function. The system can analyse programs in
a first-order subset of Lisp and we show how the system
also can be used to analyse programs in other languages.
| Original language | English |
|---|---|
| Title of host publication | FPCA '89 Conference on Functional Programming Languages and Computer Architecture. |
| Number of pages | 13 |
| Place of Publication | London, England |
| Publisher | Association for Computing Machinery |
| Publication date | 1989 |
| Pages | 144-156 |
| ISBN (Print) | 0-201-51389-7 |
| Publication status | Published - 1989 |