The characterization of FP by Bellantoni and Cook is refined and extended to define an w^2-type hierarchy T_alpha, whose finite elements T_c characterize the complexity classes DTIMEF(n^c), while those of the form T_wk+c are equivalent to DTIMEF(n_k(n^c)) (k-superexponential). The refinement allowing to capture the former classes is obtained by restricting substitution and by strengthening meanwhile the safe predicative recursion scheme. Extension to the latter is by a diagonalization scheme.
Predicative Recursion, Ramified Diagonalization and the Elementary Functions
COVINO, Emanuele;PANI, Giovanni;
2007-01-01
Abstract
The characterization of FP by Bellantoni and Cook is refined and extended to define an w^2-type hierarchy T_alpha, whose finite elements T_c characterize the complexity classes DTIMEF(n^c), while those of the form T_wk+c are equivalent to DTIMEF(n_k(n^c)) (k-superexponential). The refinement allowing to capture the former classes is obtained by restricting substitution and by strengthening meanwhile the safe predicative recursion scheme. Extension to the latter is by a diagonalization scheme.File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
