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 hiera rchies 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)