Automatic Complexity Analysis

    Publikation: Bidrag til bog/antologi/rapportBidrag til bog/antologiForskning


    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.
    TitelFPCA '89 Conference on Functional Programming Languages and Computer Architecture.
    Antal sider13
    UdgivelsesstedLondon, England
    ForlagAssociation for Computing Machinery
    ISBN (Trykt)0-201-51389-7
    StatusUdgivet - 1989

    Citer dette