JUCS - Journal of Universal Computer Science 8(1): 75-84, doi: 10.3217/jucs-008-01-0075
An Implicit Recursive Language for the Polynomial Time-space Complexity Classes
expand article infoEmanuele Covino‡, Giovanni Pani‡
‡ Università di Bari, Bari, Italy

Corresponding author: Emanuele Covino ( covino@di.uniba.it )

© Emanuele Covino, Giovanni Pani.
This article is freely available under the J.UCS Open Content License.
Citation: Covino E, Pani G (2002) An Implicit Recursive Language for the Polynomial Time-space Complexity Classes. JUCS - Journal of Universal Computer Science 8(1): 75-84. https://doi.org/10.3217/jucs-008-01-0075
Open Access
Abstract
Abstract: We define a language over an algebra of words by means of a version of predicative recursion, and we prove that it represents a resource-free characterization of the computations performed by a register machine in time O(nk), for each denite k; starting from this result, and by means of a restricted form of composition, we give a characterization of the computations of a register machine with a polynomial bound simultaneously imposed over time and space complexity.
Keywords
time-space classes, implicit computational complexity, predicative recursion