Home // COMPUTATION TOOLS 2024, The Fifteenth International Conference on Computational Logics, Algebras, Programming, Tools, and Benchmarking // View article

A Note on a Syntactical Measure of the Complexity of 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 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.

Pages: 1 to 5

Copyright: Copyright (c) IARIA, 2024

Publication date: April 14, 2024

Published in: conference

ISSN: 2308-4170

ISBN: 978-1-68558-158-9

Location: Venice, Italy

Dates: from April 14, 2024 to April 18, 2024