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 move from answering the decision problem to giving a quantitative result, namely, a tight polynomial upper bound. This paper shows how to obtain asymptotically-tight, multivariate, disjunctive polynomial bounds for this class of programs. This is a complete solution: whenever a polynomial bound exists it will be found. A pleasant surprise is that the algorithm is quite simple; but it relies on some subtle reasoning. An important ingredient in the proof is the forest factorization theorem, a strong structural result on homomorphisms into a finite monoid.
Max-plus automata (over ℕ ∪ − ∞) are finite devices that map input words to non-negative integers or − ∞. In this paper we present (a) an algorithm allowing to compute the asymptotic behaviour of max-plus automata, and (b) an application of this technique to the evaluation of the computational time complexity of programs. The size-change abstraction (SCA) is a popular program abstraction for termination analysis, and has been successfully implemented for imperative, functional and logic programs. Recently, it has been shown that SCA is also an attractive domain for the automatic analysis of the computational complexity of programs. In this paper, we provide asymptotically precise ranking functions for the special case of deterministic size-change systems. As a consequence we also obtain the result that the asymptotic complexity of deterministic size-change systems is exactly polynomial and that the exact integer exponent can be computed in PSPACE.