Syntactic characterization in Lisp of the polynomial complexity classes and hierarchy

The definition of a class C of functions is syntactic if membership to C can be decided from the construction of its elements. Syntactic characterizations of PTIMEF, of PSPACEF, of the polynomial hierarchy PH, and of its subclasses Delta(n)(p) are presented. They are obtained by progressive restrictions of recursion in Lisp, and may be regarded as predicative according to a foundational point raised by Leivant