Skip to Main Content (Press Enter)

Logo IUAV
  • ×
  • Home
  • Corsi
  • Insegnamenti
  • Professioni
  • Persone
  • Pubblicazioni
  • Strutture
  • Terza Missione
  • Attività
  • Contratti
  • Competenze
  • Attrezzature

Logo IUAV

|

UNIFIND

iuav.it
  • ×
  • Home
  • Corsi
  • Insegnamenti
  • Professioni
  • Persone
  • Pubblicazioni
  • Strutture
  • Terza Missione
  • Attività
  • Contratti
  • Competenze
  • Attrezzature
  1. Pubblicazioni

Regressive computations characterize logarithmic space

Articolo
Data di Pubblicazione:
2016
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.
Tipologia CRIS:
1.1 Articolo su Rivista
Keywords:
Logspace computable function, Recursion on notation, Regressive machine
Elenco autori:
Mazzanti, Stefano
Link alla scheda completa:
https://air.iuav.it/handle/11578/266893
Pubblicato in:
INFORMATION AND COMPUTATION
Journal
  • Dati Generali

Dati Generali

URL

https://doi.org/10.1016/j.ic.2016.07.002
  • Utilizzo dei cookie

Realizzato con VIVO | Designed by Cineca | 26.11.0.0