Tight Worst-Case Bounds for Polynomial Loop Programs
Ben-Amram, Amir M. and Hamilton, GeoffORCID: 0000-0001-5954-6444
(2019)
Tight Worst-Case Bounds for Polynomial Loop Programs.
In: International Conference on Foundations of Software Science and Computation Structures, 8-11 April 2019, Prague, Czech Republic.
ISBN 978-3-030-17126-1
In 2008, Ben-Amram, Jones and Kristiansen showed that for a simple programming language|representing non-deterministic imperative programs with bounded loops, and arithmetics limited to addition and multiplication|it is possible to decide precisely whether a program has certain growth-rate properties, in particular whether a computed value, or the program's running time, has a polynomial growth rate. A natural and intriguing problem was to improve the precision of the information obtained. This paper shows how to obtain asymptotically-tight multivariate polynomial bounds for this class of programs. This is a complete solution: whenever a polynomial bound exists it will be found.