Quasi-interpretation : a way to control ressources
Identifieur interne : 006293 ( Main/Merge ); précédent : 006292; suivant : 006294Quasi-interpretation : a way to control ressources
Auteurs : Guillaume Bonfante ; Jean-Yves Marion ; Jean-Yves MoyenSource :
English descriptors
Abstract
This paper presents in a reasoned way our works on resource analysis by quasi-interpretations. The controlled resources are typically the runtime, the runspace or the size of a result in a program execution. Quasi-interpretations assign to each program symbol a numerical function which is compatible with the computational semantics. The quasi-interpretation method offers several advantages. It allows to predict system complexity, may provide hints in order to optimize the execution, it gives resource certificates, and finally, can be automated. We propose a method to determine if a program admits or not a quasi-interpretation in a broad class which is relevant for feasible computations. By combining the quasi-interpretation method with termination tools (here term orderings), we have obtained several characterizations of complexity classes starting from Ptime and Pspace.
Links toward previous steps (curation, corpus...)
- to stream Crin, to step Corpus: 004018
- to stream Crin, to step Curation: 004018
- to stream Crin, to step Checkpoint: 000518
Links to Exploration step
CRIN:bonfante05aLe document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" wicri:score="133">Quasi-interpretation : a way to control ressources</title></titleStmt><publicationStmt><idno type="RBID">CRIN:bonfante05a</idno><date when="2005" year="2005">2005</date><idno type="wicri:Area/Crin/Corpus">004018</idno><idno type="wicri:Area/Crin/Curation">004018</idno><idno type="wicri:explorRef" wicri:stream="Crin" wicri:step="Curation">004018</idno><idno type="wicri:Area/Crin/Checkpoint">000518</idno><idno type="wicri:explorRef" wicri:stream="Crin" wicri:step="Checkpoint">000518</idno><idno type="wicri:Area/Main/Merge">006293</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en">Quasi-interpretation : a way to control ressources</title><author><name sortKey="Bonfante, Guillaume" sort="Bonfante, Guillaume" uniqKey="Bonfante G" first="Guillaume" last="Bonfante">Guillaume Bonfante</name></author><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="Moyen, Jean Yves" sort="Moyen, Jean Yves" uniqKey="Moyen J" first="Jean-Yves" last="Moyen">Jean-Yves Moyen</name></author></analytic></biblStruct></sourceDesc></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>implicit complexity</term><term>quasi-interpretations</term><term>ressource control</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en" wicri:score="2575">This paper presents in a reasoned way our works on resource analysis by quasi-interpretations. The controlled resources are typically the runtime, the runspace or the size of a result in a program execution. Quasi-interpretations assign to each program symbol a numerical function which is compatible with the computational semantics. The quasi-interpretation method offers several advantages. It allows to predict system complexity, may provide hints in order to optimize the execution, it gives resource certificates, and finally, can be automated. We propose a method to determine if a program admits or not a quasi-interpretation in a broad class which is relevant for feasible computations. By combining the quasi-interpretation method with termination tools (here term orderings), we have obtained several characterizations of complexity classes starting from Ptime and Pspace.</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 006293 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Merge/biblio.hfd -nk 006293 | 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é= CRIN:bonfante05a
|texte= Quasi-interpretation : a way to control ressources
}}
| This area was generated with Dilib version V0.6.33. |  |