Asymptotic speedups, bisimulation and distillation (Work in progress)

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

  • Neil Jones
  • G. W. Hamilton

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 languageEnglish
Title of host publicationPerspectives of system informatics : 9th International Ershov Informatics Conference, PSI 2014, St. Petersburg, Russia, June 24-27, 2014. Revised Selected Papers
EditorsAndrei Voronkov, Irina Virbitskaite
Number of pages9
PublisherSpringer
Publication date2015
Pages177-185
ISBN (Print)978-3-662-46822-7
ISBN (Electronic)978-3-662-46823-4
DOIs
Publication statusPublished - 2015
Event9th International Ershov Informatics Conference on Perspectives of System Informatics, PSI 2014 - St. Petersburg, Russian Federation
Duration: 24 Jun 201427 Jun 2014

Conference

Conference9th International Ershov Informatics Conference on Perspectives of System Informatics, PSI 2014
LandRussian Federation
BySt. Petersburg
Periode24/06/201427/06/2014
SeriesLecture Notes in Computer Science
Volume8974
ISSN0302-9743

ID: 160888955