Automated Complexity Analysis via Transformations

This project is concerned with analysing the complexity of programs. This is a highly important subject, since the complexity of a program essentially determines its usefulness. We aim at a tool that performs a static program analysis and that can handle existing programming languages, not only toy languages.The two main goals of the project are

  • to obtain automated complexity preserving transformations from Java and Prolog into term rewrite systems (TRSs for short), and
  • to advance the state of the art of automated complexity analysis of term rewrite systems.

In these goals we seek precise asymptotic polynomial bounds that may be non-linear. Through the abstract representation of programs as rewrite system our analysis enables disjunctive bounds and through the use of a dedicated combination framework we achieve compositionality and thus effectivity of the method.
We summarise the goals of the project as follows: Advance the state of the art of complexity analysis of programs by investigating automated runtime complexity analysis via transformations.


Start of Project: October 1, 2013

  • Stéphane Gimenez
  • Andreas Kochesser
  • Georg Moser
  • David Obwaller
  • Thomas Powell
  • Michael Schaper
  • Maria Schett
  • Manuel Schneckenreither
  • Logic, Complexity and Automation, September 5-7, 2016, Obergurgl, Austria
  • Two Faces of Complexity 2014, Saturday, July 12, 2014, Vienna, Austria

Currently there are no vacancies in the project.

FWF "single Project" project number

P 25781-N15


Nach oben scrollen