In earlier work of Kristiansen and Niggl the polynomial-time computable functions were characterized by stack programs of $\mu$-measure 0, and the linear-space computable functions by loop programs of $\mu$-measure 0. Until recently, an open problem was how to extend these characterizations to programs with user-friendly basic instructions, such as assignment statements, and with mixed data structures. It is shown how to strengthen the above characterizations to imperative programs built from arbitrary basic instructions by sequencing and by if-then-else and for-do statements. These programs operate on variables, each of which may represent any data structure such as stacks, registers, trees, or graphs. The paper presents a new method of certifying "polynomial size boundedness" of such imperative programs under the natural assumption that the basic instructions used are polynomially size bounded, too. The certificate for a program ${\tt P}$ with variables among ${\tt X}_{1}, \ldots, {\tt X}_{n}$ will be an $(n+1)\times (n+1)$ matrix $M({\tt P})$ over the finite set $\{ 0, 1, \infty\}$. It is shown that certified string programs (i.e., stack programs, but with any polynomial-time computable basic instructions) exactly compute the functions in {\sc fptime}. Accordingly, certified general loop programs (using any linear-space computable basic instructions) exactly compute the functions in {\sc flinspace}. Furthermore, it is shown that certified power string programs (i.e., string programs, but built from polynomial-space computable basic instructions and extended by power loop statements) exactly compute the polynomial-space computable functions in {\sc fpspace}. In addition, examples of certified "natural" (implementations of) algorithms, such as insertion-sort or binary addition and multiplication, are given.

Traditional results in subrecursion theory are integrated with the recent work in "predicative recursion" by defining a simple ranking $\rho$ of all primitive recursive functions. The hierarchy defined by this ranking coincides with the Grzegorczyk hierarchy at and above the linear-space level. Thus, the result is like an extension of the Schwichtenberg--Müller theorems. When primitive recursion is replaced by recursion on notation, the same series of classes is obtained except with the polynomial time computable functions at the first level.