Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [28 references]  Display  Hide  Download

https://hal.inria.fr/inria-00332390
Contributor : Romain Péchoux <>
Submitted on : Monday, October 20, 2008 - 6:10:17 PM
Last modification on : Tuesday, May 5, 2020 - 5:02:15 PM
Long-term archiving on: : Monday, June 7, 2010 - 8:55:10 PM

File

paper69.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Jean-Yves Marion, Romain Péchoux. A Characterization of NCk by First Order Functional Programs. 5th International Conference on Theory and Applications of Models of Computation - TAMC 2008, Xidian University, Apr 2008, Xian, China. pp.136-147, ⟨10.1007/978-3-540-79228-4⟩. ⟨inria-00332390⟩

Share

Metrics

Record views

292

Files downloads

306