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

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.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11586/13089
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? ND
social impact