Esiti della ricerca
Digita i termini da ricercare in tutto l'archivio:

Regressive computations characterize logarithmic space

Mazzanti, Stefano Regressive computations characterize logarithmic space. Working Paper. submitted. (Sottomesso)

full text

[img]
Anteprima
Documento PDF - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
385Kb

Abstract

We consider the function class E generated by the constant functions, the projection functions, the predecessor function, the substitution operator and the recursion on notation operator. Furthermore, we introduce regressive machines, i. e. register machines which have the division by 2 and the predecessor as basic operations. We show that E is the class of functions computable by regressive machines and that the sharply bounded functions of E coincide with the sharply bounded logspace computable functions.

Tipologia del documento:Monografia (Working Paper)
Soggetti:Area 01 - Scienze matematiche e informatiche > INF/01 Informatica
Struttura:Dipartimenti > Dcp Dipartimento di culture del progetto
Codice ID:414
Depositato da :Stefano Mazzanti
Depositato il :10 Dic 2014 07:39
Ultima modifica:10 Dic 2014 07:39

Solo per Staff dell'archivio: Gestione del Documento