Go home now Header Background Image
Submission Procedure
share: |
Follow us
Volume 8 / Issue 1

available in:   PDF (252 kB) PS (66 kB)
Similar Docs BibTeX   Write a comment
Links into Future
DOI:   10.3217/jucs-008-01-0075


An Implicit Recursive Language for the Polynomial Time-space Complexity Classes

Emanuele Covino (Dipartimento di Informatica dell'Università di Bari, Italy)

Giovanni Pani (Dipartimento di Informatica dell'Università di Bari, Italy)


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: implicit computational complexity, predicative recursion, time-space classes

Categories: F.1.3