Static complexity analysis of higher order programs

James Emil Avery; Lars Kristiansen; Jean-Yves Moyen

doi:10.1007/978-3-642-15331-0_6

Static complexity analysis of higher order programs

James Emil Avery, Lars Kristiansen, Jean-Yves Moyen

Datalogisk Institut

2 Citationer (Scopus)

Abstract

In the paper's first part, we present a method for certifying that the values computed by a first order imperative program will be bounded by polynomials in the program's inputs. Our method does not yield concrete polynomials, but shows existence of polynomial bounds and upper bounds to their polynomial degrees. In the second part of the paper, we lift our method to allow analysis of higher order programs.

Originalsprog	Engelsk
Titel	Foundational and Practical Aspects of Resource Analysis : First International Workshop, FOPARA 2009, Eindhoven, The Netherlands, November 6, 2009, Revised Selected Papers
Redaktører	Marko van Eekelen, Olha Shkaravska
Antal sider	16
Forlag	Springer
Publikationsdato	2010
Sider	84-99
ISBN (Trykt)	978-3-642-15330-3
ISBN (Elektronisk)	978-3-642-15331-0
DOI	https://doi.org/10.1007/978-3-642-15331-0_6
Status	Udgivet - 2010
Begivenhed	1st International Workshop on Foundational and Practical Aspects of Resource Analysis - Eindhoven, Holland Varighed: 6 nov. 2009 → 6 nov. 2009 Konferencens nummer: 1

Konference

Konference	1st International Workshop on Foundational and Practical Aspects of Resource Analysis
Nummer	1
Land/Område	Holland
By	Eindhoven
Periode	06/11/2009 → 06/11/2009

Navn	Lecture notes in computer science
Vol/bind	6324
ISSN	0302-9743

Adgang til dokumentet

10.1007/978-3-642-15331-0_6

Citationsformater

Avery, J. E., Kristiansen, L., & Moyen, J.-Y. (2010). Static complexity analysis of higher order programs. I M. van Eekelen, & O. Shkaravska (red.), Foundational and Practical Aspects of Resource Analysis: First International Workshop, FOPARA 2009, Eindhoven, The Netherlands, November 6, 2009, Revised Selected Papers (s. 84-99). Springer. https://doi.org/10.1007/978-3-642-15331-0_6

Static complexity analysis of higher order programs. / Avery, James Emil; Kristiansen, Lars; Moyen, Jean-Yves.
Foundational and Practical Aspects of Resource Analysis: First International Workshop, FOPARA 2009, Eindhoven, The Netherlands, November 6, 2009, Revised Selected Papers. red. / Marko van Eekelen; Olha Shkaravska. Springer, 2010. s. 84-99 (Lecture notes in computer science, Bind 6324).

Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › peer review

Avery, JE, Kristiansen, L & Moyen, J-Y 2010, Static complexity analysis of higher order programs. i M van Eekelen & O Shkaravska (red), Foundational and Practical Aspects of Resource Analysis: First International Workshop, FOPARA 2009, Eindhoven, The Netherlands, November 6, 2009, Revised Selected Papers. Springer, Lecture notes in computer science, bind 6324, s. 84-99, 1st International Workshop on Foundational and Practical Aspects of Resource Analysis, Eindhoven, Holland, 06/11/2009. https://doi.org/10.1007/978-3-642-15331-0_6

Avery JE, Kristiansen L, Moyen JY. Static complexity analysis of higher order programs. I van Eekelen M, Shkaravska O, red., Foundational and Practical Aspects of Resource Analysis: First International Workshop, FOPARA 2009, Eindhoven, The Netherlands, November 6, 2009, Revised Selected Papers. Springer. 2010. s. 84-99. (Lecture notes in computer science, Bind 6324). doi: 10.1007/978-3-642-15331-0_6

Avery, James Emil ; Kristiansen, Lars ; Moyen, Jean-Yves. / Static complexity analysis of higher order programs. Foundational and Practical Aspects of Resource Analysis: First International Workshop, FOPARA 2009, Eindhoven, The Netherlands, November 6, 2009, Revised Selected Papers. red. / Marko van Eekelen ; Olha Shkaravska. Springer, 2010. s. 84-99 (Lecture notes in computer science, Bind 6324).

@inproceedings{6c5de2de99db4784b7f7e6687d793175,

title = "Static complexity analysis of higher order programs",

abstract = "In the paper's first part, we present a method for certifying that the values computed by a first order imperative program will be bounded by polynomials in the program's inputs. Our method does not yield concrete polynomials, but shows existence of polynomial bounds and upper bounds to their polynomial degrees. In the second part of the paper, we lift our method to allow analysis of higher order programs.",

author = "Avery, {James Emil} and Lars Kristiansen and Jean-Yves Moyen",

year = "2010",

doi = "10.1007/978-3-642-15331-0_6",

language = "English",

isbn = "978-3-642-15330-3",

series = "Lecture notes in computer science",

publisher = "Springer",

pages = "84--99",

editor = "{van Eekelen}, Marko and Olha Shkaravska",

booktitle = "Foundational and Practical Aspects of Resource Analysis",

note = "1st International Workshop on Foundational and Practical Aspects of Resource Analysis, FOPARA 2009 ; Conference date: 06-11-2009 Through 06-11-2009",

}

TY - GEN

T1 - Static complexity analysis of higher order programs

AU - Avery, James Emil

AU - Kristiansen, Lars

AU - Moyen, Jean-Yves

N1 - Conference code: 1

PY - 2010

Y1 - 2010

N2 - In the paper's first part, we present a method for certifying that the values computed by a first order imperative program will be bounded by polynomials in the program's inputs. Our method does not yield concrete polynomials, but shows existence of polynomial bounds and upper bounds to their polynomial degrees. In the second part of the paper, we lift our method to allow analysis of higher order programs.

AB - In the paper's first part, we present a method for certifying that the values computed by a first order imperative program will be bounded by polynomials in the program's inputs. Our method does not yield concrete polynomials, but shows existence of polynomial bounds and upper bounds to their polynomial degrees. In the second part of the paper, we lift our method to allow analysis of higher order programs.

U2 - 10.1007/978-3-642-15331-0_6

DO - 10.1007/978-3-642-15331-0_6

M3 - Article in proceedings

SN - 978-3-642-15330-3

T3 - Lecture notes in computer science

SP - 84

EP - 99

BT - Foundational and Practical Aspects of Resource Analysis

A2 - van Eekelen, Marko

A2 - Shkaravska, Olha

PB - Springer

T2 - 1st International Workshop on Foundational and Practical Aspects of Resource Analysis

Y2 - 6 November 2009 through 6 November 2009

ER -

Static complexity analysis of higher order programs

Abstract

Konference

Adgang til dokumentet

Fingeraftryk

Citationsformater