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

Department of Computer Science

2 Citations (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.

Original language	English
Title of host publication	Foundational and Practical Aspects of Resource Analysis : First International Workshop, FOPARA 2009, Eindhoven, The Netherlands, November 6, 2009, Revised Selected Papers
Editors	Marko van Eekelen, Olha Shkaravska
Number of pages	16
Publisher	Springer
Publication date	2010
Pages	84-99
ISBN (Print)	978-3-642-15330-3
ISBN (Electronic)	978-3-642-15331-0
DOIs	https://doi.org/10.1007/978-3-642-15331-0_6
Publication status	Published - 2010
Event	1st International Workshop on Foundational and Practical Aspects of Resource Analysis - Eindhoven, Netherlands Duration: 6 Nov 2009 → 6 Nov 2009 Conference number: 1

Conference

Conference	1st International Workshop on Foundational and Practical Aspects of Resource Analysis
Number	1
Country/Territory	Netherlands
City	Eindhoven
Period	06/11/2009 → 06/11/2009

Series	Lecture notes in computer science
Volume	6324
ISSN	0302-9743

Access to Document

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

Cite this

Avery, J. E., Kristiansen, L., & Moyen, J.-Y. (2010). Static complexity analysis of higher order programs. In M. van Eekelen, & O. Shkaravska (Eds.), Foundational and Practical Aspects of Resource Analysis: First International Workshop, FOPARA 2009, Eindhoven, The Netherlands, November 6, 2009, Revised Selected Papers (pp. 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. ed. / Marko van Eekelen; Olha Shkaravska. Springer, 2010. p. 84-99 (Lecture notes in computer science, Vol. 6324).

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

Avery, JE, Kristiansen, L & Moyen, J-Y 2010, Static complexity analysis of higher order programs. in M van Eekelen & O Shkaravska (eds), 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, vol. 6324, pp. 84-99, 1st International Workshop on Foundational and Practical Aspects of Resource Analysis, Eindhoven, Netherlands, 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. In van Eekelen M, Shkaravska O, editors, Foundational and Practical Aspects of Resource Analysis: First International Workshop, FOPARA 2009, Eindhoven, The Netherlands, November 6, 2009, Revised Selected Papers. Springer. 2010. p. 84-99. (Lecture notes in computer science, Vol. 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. editor / Marko van Eekelen ; Olha Shkaravska. Springer, 2010. pp. 84-99 (Lecture notes in computer science, Vol. 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

Conference

Access to Document

Fingerprint

Cite this