A Characterization of NCk by First Order Functional Programs

Jean-Yves Marion 1 Romain Péchoux 1
1 CARTE - Theoretical adverse computations, and safety
Inria Nancy - Grand Est, LORIA - FM - Department of Formal Methods
Abstract : This paper is part of a research on static analysis in order to predict program resources and belongs to the implicit computational complexity line of research. It presents intrinsic characterizations of the classes of functions, which are computable in NCk, that is by a uniform, poly-logarithmic depth and polynomial size family of circuits, using first order functional programs. Our characterizations are new in terms of first order functional programming language and extend the characterization of NC1 in [9]. These characterizations are obtained using a complexity measure, the sup-interpretation, which gives upper bounds on the size of computed values and captures a lot of program schemas.
Type de document :
Communication dans un congrès
Manindra Agrawal, Dingzhu Du, Zhenhua Duan and Angsheng Li. 5th International Conference on Theory and Applications of Models of Computation - TAMC 2008, Apr 2008, Xian, China. Springer Berlin / Heidelberg, 4978, pp.136-147, 2008, Lecture Notes in Computer Science. 〈10.1007/978-3-540-79228-4〉
Liste complète des métadonnées

Littérature citée [28 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00332390
Contributeur : Romain Péchoux <>
Soumis le : lundi 20 octobre 2008 - 18:10:17
Dernière modification le : jeudi 11 janvier 2018 - 06:21:25
Document(s) archivé(s) le : lundi 7 juin 2010 - 20:55:10

Fichier

paper69.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Jean-Yves Marion, Romain Péchoux. A Characterization of NCk by First Order Functional Programs. Manindra Agrawal, Dingzhu Du, Zhenhua Duan and Angsheng Li. 5th International Conference on Theory and Applications of Models of Computation - TAMC 2008, Apr 2008, Xian, China. Springer Berlin / Heidelberg, 4978, pp.136-147, 2008, Lecture Notes in Computer Science. 〈10.1007/978-3-540-79228-4〉. 〈inria-00332390〉

Partager

Métriques

Consultations de la notice

230

Téléchargements de fichiers

91