On the computational complexity of imperative programming languages

AbstractTwo restricted imperative programming languages are considered: One is a slight modification of a loop language studied intensively in the literature, the other is a stack programming language over an arbitrary but fixed alphabet, supporting a suitable loop concept over stacks. The paper presents a purely syntactical method for analysing the impact of nesting loops on the running time. This gives rise to a uniform measure μ on both loop and stack programs, that is, a function that assigns to each such program P a natural number μ(P) computable from the syntax of P.It is shown that stack programs of μ-measure n compute exactly those functions computed by a Turing machine whose running time lies in Grzegorczyk class En+2. In particular, stack programs of μ-measure 0 compute precisely the polynomial-time computable functions.Furthermore, it is shown that loop programs of μ-measure n compute exactly the functions in En+2. In particular, loop programs of μ-measure 0 compute precisely the linear-space computable functions