Andreas Goerdt and Helmut Seidl. **Characterizing Complexity Classes by Higher Type Primitive Recursive Definitions, Part II**. In Jürgen Dassow and Jozef Kelemen, editors, *Aspects and Prospects of Theoretical Computer Scienc*, volume 464 of *Lecture Notes in Computer Science*, pages 148-158, Smolenice, Czechoslovakia, November 1990. Springer.

Higher type primitive recursive definitions (also known as Gödel's system T) defining first-order functions (i.e. functions of type ind...indind, ind for individuals, higher types occur in between) can be classified into an infinite syntactic hierarchy: A definition is in the n'th stage of this hierarchy, a so called rank-n-definition, iff n is an upper bound on the levels of the types occurring in it. We interpret these definitions over finite structures and show for : Rank-(2n+2)-definitions characterize (in the sense of [Gu83], say) the complexity class DTIME whereas rank-(2n+3)-definitions characterize DSPACE (here , . This extends the results that rank-1-definitions characterize LOGSPACE [Gu83], rank-2-definitions characterize PTIME, rank-3-definitions characterize PSPACE, rank-4-definitions characterize EXPTIME [Go89a]

Reference: Bibtex The original publication is available at www.springerlink.com