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 register machines, which have division by 2 and the predecessor on natural numbers as basic operations. We show that E is the class of functions computable by regressive machines and that the sharply bounded functions (functions with logarithmic size values) of E coincide with the sharply bounded logspace computable functions.

Regressive computations characterize logarithmic space

Mazzanti, Stefano
2016-01-01

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 register machines, which have division by 2 and the predecessor on natural numbers as basic operations. We show that E is the class of functions computable by regressive machines and that the sharply bounded functions (functions with logarithmic size values) of E coincide with the sharply bounded logspace computable functions.
File in questo prodotto:
File Dimensione Formato  
Finale_logspace31.pdf

non disponibili

Descrizione: Articolo principale
Tipologia: Documento in Pre-print
Licenza: Accesso ristretto
Dimensione 433.89 kB
Formato Adobe PDF
433.89 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11578/266893
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact