Home // International Journal On Advances in Intelligent Systems, volume 8, numbers 3 and 4, 2015 // View article

Predicative Recursion, Diagonalization, and Slow-growing Hierarchies of Time-bounded Programs

Authors:
Emanuele Covino
Giovanni Pani

Keywords: Time/space complexity classes; Implicit computational complexity; Predicative recursion; Diagonalization

Abstract:
We define a version of predicative recursion, a related programming language, and a hierarchy of classes of programs that represents a resource-free characterization of register machines computing their output within polynomial time O(n^k), for each finite k. Then, we introduce an operator of diagonalization, that allows us to extend the previous hierarchy and to capture the register machines with computing time bounded by an exponential limit O(n^(n^k)). Finally, by means of a restriction on composition of programs, we characterize the register machines with a polynomial bound imposed over time and space complexity, simultaneously.

Pages: 339 to 346

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

Publication date: December 30, 2015

Published in: journal

ISSN: 1942-2679