A note on a syntactical measure of the complexity of programs

We introduce a programming language operating on stacks and a syntactical measure σ, such that a natural number σ(P) is assigned to each program P. The measure considers how the presence of loops defined over size-increasing (and non-size-increasing) subprograms influences the complexity of the program itself. Functions computed by a program of σ- measure n are exactly those computable by a Turing machine with running time in E^n+2 (the n+2-th Grzegorczyk class). Programs of σ-measure 0 compute the polynomial-time computable functions. Thus, we have a syntactical characterization of the functions belonging to the Grzegorczyk hierarchy; this result represents an improvement with respect to previous similar results.