Projects per year
Abstract
We provide an overview of the FET-Open Project CerCo (‘Certified Complexity’). Our main achievement is the development of a technique for analysing non-functional properties of programs (time, space) at the source level with little or no loss of accuracy and a small trusted code base. The core component is a C compiler, verified in Matita, that produces an instrumented copy of the source code in addition to generating object code. This instrumentation exposes, and tracks precisely, the actual (non-asymptotic) computational cost of the input program at the source level. Untrusted invariant generators and trusted theorem provers may then be used to compute and certify the parametric execution time of the code.
Original language | English |
---|---|
Title of host publication | Foundational and Practical Aspects of Resource Analysis |
Subtitle of host publication | Revised Selected Papers from the Third International Workshop, FOPARA 2013, Bertinoro, Italy, August 29-31, 2013 |
Publisher | Springer International Publishing |
Pages | 1-18 |
Number of pages | 18 |
ISBN (Electronic) | 978-3-319-12466-7 |
ISBN (Print) | 978-3-319-12465-0 |
DOIs | |
Publication status | Published - 2014 |
Publication series
Name | Lecture Notes in Computer Science |
---|---|
Volume | 8552 |
ISSN (Print) | 0302-9743 |
Fingerprint
Dive into the research topics of 'Certified Complexity (CerCo)'. Together they form a unique fingerprint.Projects
- 1 Finished
Profiles
-
Brian Campbell
- School of Informatics - Senior Researcher
- Laboratory for Foundations of Computer Science
- Foundations of Computation
Person: Academic: Research Active (Research Assistant)
-
Ian Stark
- School of Informatics - Senior Lecturer
- Laboratory for Foundations of Computer Science
- Foundations of Computation
Person: Academic: Research Active