Abstract : Restricted recursion schemes offer a nice framework for the characterization of computability and complexity classes. In this talk, we will survey some well known results on this subject and introduce a new approach based on (Ordinary) Difference Equations as a tool for computation and algorithm design. We will present the general theory of discrete ODEs for computation theory, illustrate this with various examples of algorithms, and provide a simple  characterization of polynomial time computable functions.

L’exposé est disponible ici.