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.