Programming Languages Capturing Complexity Classes

We investigate an imperative and a functional programming language. The computational power of fragments of these languages induce two hierarchies of com-plexity classes. Our first main theorem says that these hierarchies match, level by level, a complexity-theoretic alternating space-time hierarchy known from the literature. Our second main theorems says that a slightly different complexity-theoretic hierarchy (the Goerdt-Seidl hierarchy) also can be captured by hierarchies induced by fragments of the programming languages. Well known complexity classes like logspace, linspace, p, pspace, etc., occur in the hierarchies