We give a recursion-theoretic characterization of the complexity classes NC k for  k i¾? 1. In the spirit of implicit computational complexity, it uses no explicit bounds in the recursion and also no separation of variables is needed. It is based on three recursion schemes, one corresponds to time (time iteration), one to space allocation (explicit structural recursion) and one to internal computations (mutual in place recursion). This is, to our knowledge, the first exact characterization of NC k by function algebra over infinite domains in implicit complexity.
['Guillaume Bonfante', 'Reinhard Kahle', 'Jean-Yves Marion', 'Isabel Oitavem']
Recursion Schemata for NCk