Asymptotic speedups, bisimulation and distillation (Work in progress)
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Distillation is a fully automatic program transformation that can yield superlinear program speedups. Bisimulation is a key to the proof that distillation is correct, i.e., preserves semantics. However the proof, based on observational equivalence, is insensitive to program running times. This paper shows how distillation can give superlinear speedups on some “old chestnut” programs well-known from the early program transformation literature: naive reverse, factorial sum, and Fibonacci.
Original language | English |
---|---|
Title of host publication | Perspectives of system informatics : 9th International Ershov Informatics Conference, PSI 2014, St. Petersburg, Russia, June 24-27, 2014. Revised Selected Papers |
Editors | Andrei Voronkov, Irina Virbitskaite |
Number of pages | 9 |
Publisher | Springer |
Publication date | 2015 |
Pages | 177-185 |
ISBN (Print) | 978-3-662-46822-7 |
ISBN (Electronic) | 978-3-662-46823-4 |
DOIs | |
Publication status | Published - 2015 |
Event | 9th International Ershov Informatics Conference on Perspectives of System Informatics, PSI 2014 - St. Petersburg, Russian Federation Duration: 24 Jun 2014 → 27 Jun 2014 |
Conference
Conference | 9th International Ershov Informatics Conference on Perspectives of System Informatics, PSI 2014 |
---|---|
Land | Russian Federation |
By | St. Petersburg |
Periode | 24/06/2014 → 27/06/2014 |
Series | Lecture Notes in Computer Science |
---|---|
Volume | 8974 |
ISSN | 0302-9743 |
ID: 160888955