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:
Pubblicato in: