Automatic Complexity Analysis

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

    Resumé

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

    Citer dette

    Rosendahl, M. (1989). Automatic Complexity Analysis. I FPCA '89 Conference on Functional Programming Languages and Computer Architecture. (s. 144-156). London, England: Association for Computing Machinery.
    Rosendahl, Mads. / Automatic Complexity Analysis. FPCA '89 Conference on Functional Programming Languages and Computer Architecture.. London, England : Association for Computing Machinery, 1989. s. 144-156
    @inbook{13ac89a052be11dba4bc000ea68e967b,
    title = "Automatic Complexity Analysis",
    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.",
    author = "Mads Rosendahl",
    year = "1989",
    language = "English",
    isbn = "0-201-51389-7",
    pages = "144--156",
    booktitle = "FPCA '89 Conference on Functional Programming Languages and Computer Architecture.",
    publisher = "Association for Computing Machinery",

    }

    Rosendahl, M 1989, Automatic Complexity Analysis. i FPCA '89 Conference on Functional Programming Languages and Computer Architecture.. Association for Computing Machinery, London, England, s. 144-156.

    Automatic Complexity Analysis. / Rosendahl, Mads.

    FPCA '89 Conference on Functional Programming Languages and Computer Architecture.. London, England : Association for Computing Machinery, 1989. s. 144-156.

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

    TY - CHAP

    T1 - Automatic Complexity Analysis

    AU - Rosendahl, Mads

    PY - 1989

    Y1 - 1989

    N2 - 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.

    AB - 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.

    M3 - Book chapter

    SN - 0-201-51389-7

    SP - 144

    EP - 156

    BT - FPCA '89 Conference on Functional Programming Languages and Computer Architecture.

    PB - Association for Computing Machinery

    CY - London, England

    ER -

    Rosendahl M. Automatic Complexity Analysis. I FPCA '89 Conference on Functional Programming Languages and Computer Architecture.. London, England: Association for Computing Machinery. 1989. s. 144-156