The characterization of FP by Bellantoni and Cook is refined and extended to define an ω2-type hierarchy Tα, whose finite elements Tc characterize the complexity classes DTIMEF (nc), while those of the form Tωk+ c are equivalent to DTIMEF (nk (nc))(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, E.;Cozza, V.;
2007-01-01
Abstract
The characterization of FP by Bellantoni and Cook is refined and extended to define an ω2-type hierarchy Tα, whose finite elements Tc characterize the complexity classes DTIMEF (nc), while those of the form Tωk+ c are equivalent to DTIMEF (nk (nc))(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.
