A Characterization of NC k by First Order Functional Programs
Identifieur interne : 004548 ( Main/Merge ); précédent : 004547; suivant : 004549A Characterization of NC k by First Order Functional Programs
Auteurs : Jean-Yves Marion [France] ; Romain Péchoux [France]Source :
- Lecture Notes in Computer Science [ 0302-9743 ]
Abstract
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 $\textit{NC}^{\textit{k}}$ , 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 $\textit{NC}^{\textit{1}}$ 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.
Url:
DOI: 10.1007/978-3-540-79228-4_12
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 002E90
- to stream Istex, to step Curation: 002E52
- to stream Istex, to step Checkpoint: 000E65
Links to Exploration step
ISTEX:C597E8512D198B2355EF08F719E0183A5565D729Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">A Characterization of NC k by First Order Functional Programs</title><author><name sortKey="Marion, Jean Yves" sort="Marion, Jean Yves" uniqKey="Marion J" first="Jean-Yves" last="Marion">Jean-Yves Marion</name></author><author><name sortKey="Pechoux, Romain" sort="Pechoux, Romain" uniqKey="Pechoux R" first="Romain" last="Péchoux">Romain Péchoux</name></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:C597E8512D198B2355EF08F719E0183A5565D729</idno><date when="2008" year="2008">2008</date><idno type="doi">10.1007/978-3-540-79228-4_12</idno><idno type="url">https://api.istex.fr/ark:/67375/HCB-NXKPM5NZ-Z/fulltext.pdf</idno><idno type="wicri:Area/Istex/Corpus">002E90</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">002E90</idno><idno type="wicri:Area/Istex/Curation">002E52</idno><idno type="wicri:Area/Istex/Checkpoint">000E65</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">000E65</idno><idno type="wicri:doubleKey">0302-9743:2008:Marion J:a:characterization:of</idno><idno type="wicri:Area/Main/Merge">004548</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">A Characterization of <hi rend="italic">NC</hi><hi rend="superscript"><hi rend="italic">k</hi></hi> by First Order Functional Programs</title><author><name sortKey="Marion, Jean Yves" sort="Marion, Jean Yves" uniqKey="Marion J" first="Jean-Yves" last="Marion">Jean-Yves Marion</name><affiliation wicri:level="3"><country xml:lang="fr">France</country><wicri:regionArea>Loria-INPL, École Nationale Supérieure des Mines de Nancy, B.P. 239, 54506, Vandœuvre-lès-Nancy Cedex</wicri:regionArea><placeName><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region><settlement type="city">Vandœuvre-lès-Nancy</settlement></placeName></affiliation><affiliation wicri:level="1"><country wicri:rule="url">France</country></affiliation></author><author><name sortKey="Pechoux, Romain" sort="Pechoux, Romain" uniqKey="Pechoux R" first="Romain" last="Péchoux">Romain Péchoux</name><affiliation wicri:level="3"><country xml:lang="fr">France</country><wicri:regionArea>Loria-INPL, École Nationale Supérieure des Mines de Nancy, B.P. 239, 54506, Vandœuvre-lès-Nancy Cedex</wicri:regionArea><placeName><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region><settlement type="city">Vandœuvre-lès-Nancy</settlement></placeName></affiliation><affiliation wicri:level="1"><country wicri:rule="url">France</country></affiliation></author></analytic><monogr></monogr><series><title level="s" type="main" xml:lang="en">Lecture Notes in Computer Science</title><idno type="ISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="ISSN">0302-9743</idno></series></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0302-9743</idno></seriesStmt></fileDesc><profileDesc><textClass></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">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 $\textit{NC}^{\textit{k}}$ , 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 $\textit{NC}^{\textit{1}}$ 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.</div></front></TEI></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Merge
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 004548 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Merge/biblio.hfd -nk 004548 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Main
|étape= Merge
|type= RBID
|clé= ISTEX:C597E8512D198B2355EF08F719E0183A5565D729
|texte= A Characterization of NC k by First Order Functional Programs
}}
| This area was generated with Dilib version V0.6.33. |  |