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.

Autore Pugliese

• Covino Emanuele , Pani Giovanni

Tutti gli autori

• COVINO E.;PANI G.

Titolo volume/Rivista

Non Disponibile

Anno di pubblicazione

2015

ISSN

1942-2679

ISBN

Non Disponibile

Numero di citazioni Wos

Nessuna citazione

Ultimo Aggiornamento Citazioni

Non Disponibile

Numero di citazioni Scopus

Non Disponibile

Ultimo Aggiornamento Citazioni

Non Disponibile

Settori ERC

Non Disponibile

Codici ASJC

Non Disponibile