Implicit computational complexity : program interpretations
Complexité implicite des calculs : interprétation de programmes
Résumé
Our thesis is a development of implicit computational complexity. As defined by Daniel Leivant, the problem is to characterize the complexity of programs without any explicit reference to some computational model. We show that interpretations of programs are a good tool in this context. Both theoretical and practical issues are dealt.
L'étude que nous proposons s'inscrit dans le cadre de la complexité implicite des calculs. Selon Daniel Leivant, il s'agit de donner des caractérisations de la complexité sans faire de référence explicite à un modèle de calcul. Nous montrons que les interprétations de programmes sont un bon outil d'analyse dans ce contexte. Les aspects théoriques et pratiques sont abordés.
Domaines
Complexité [cs.CC]
Loading...