Home // International Journal On Advances in Systems and Measurements, volume 18, numbers 1 and 2, 2025 // View article

A Note on a Syntactical Measure of the Time-Space Complexity of Stack Programs

Authors:
Emanuele Covino

Keywords: Polynomial-Time Complexity, Grzegorczyk Hierarchy, Imperative Programming Languages, Stack Programs

Abstract:
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.

Pages: 1 to 7

Copyright: Copyright (c) to authors, 2025. Used with permission.

Publication date: June 30, 2025

Published in: journal

ISSN: 1942-261x