A Note on a Syntactical Measure of the Time-Space Complexity of Stack 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 a size-increasing (and non-size-increasing) subprogram 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 functions belonging to the Grzegorczyk hierarchy; this result represents an improvement with respect to previous similar results. We then extend this approach to the definition of programs with simultaneous time and space bounds in the same hierarchy.