Recursion Schemata for NCk

Guillaume Bonfante (1) , Reinhard Kahle (2) , Jean-Yves Marion (1) , Isabel Oitavem (2)

1 CARTE - Theoretical adverse computations, and safety
2 DI - Departamento de Informática

We give a recursion-theoretic characterization of the complexity classes NC k for k ≥ 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.

Domaines: Logique en informatique [cs.LO]

Guillaume Bonfante, Reinhard Kahle, Jean-Yves Marion, Isabel Oitavem. Recursion Schemata for NCk. 22nd International Workshop, CSL 2008, 17th Annual Conference of the EACSL, Bertinoro, Italy, September 16-19, 2008. Proceedings, Sep 2008, Bertinoro, Italy. pp.49-63, ⟨10.1007/978-3-540-87531-4_6⟩. ⟨hal-00342366⟩