A resource-free characterization of some complexity clesses is given, by means of predicative recursion and constructive diagonalization schemes, and of restrictions of substitution. Among other classes, we predicatively harmonize in the same hierarchy PTIMEF, the class E of the elementary functions, and the classes DTIMESPACEF(n^p, n^q).
Extending the Implicit Computational Complexity Approach to the sub-elementary time-space classes
COVINO, Emanuele;PANI, Giovanni;
2000-01-01
Abstract
A resource-free characterization of some complexity clesses is given, by means of predicative recursion and constructive diagonalization schemes, and of restrictions of substitution. Among other classes, we predicatively harmonize in the same hierarchy PTIMEF, the class E of the elementary functions, and the classes DTIMESPACEF(n^p, n^q).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.
