Quasi-interpretations a way to control resources
Identifieur interne : 002848 ( Main/Merge ); précédent : 002847; suivant : 002849Quasi-interpretations a way to control resources
Auteurs : G. Bonfante [France] ; J.-Y. Marion [France] ; J.-Y. Moyen [France]Source :
- Theoretical computer science [ 0304-3975 ] ; 2011.
Descripteurs français
- Pascal (Inist)
English descriptors
- KwdEn :
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 allow the analysis of system complexity. A quasi-interpretation is a numerical assignment, which provides an upper bound on computed functions and which is compatible with the program operational semantics. The quasi-interpretation method offers several advantages: (i) It provides hints in order to optimize an execution, (ii) it gives resource certificates, and (iii) finding quasi-interpretations is decidable for a broad class which is relevant for feasible computations. By combining the quasi-interpretation method with termination tools (here term orderings), we obtained several characterizations of complexity classes starting from PTIME and PSPACE.
Links toward previous steps (curation, corpus...)
- to stream PascalFrancis, to step Corpus: 000152
- to stream PascalFrancis, to step Curation: 000861
- to stream PascalFrancis, to step Checkpoint: 000124
Links to Exploration step
Pascal:11-0248946Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" level="a">Quasi-interpretations a way to control resources</title><author><name sortKey="Bonfante, G" sort="Bonfante, G" uniqKey="Bonfante G" first="G." last="Bonfante">G. Bonfante</name><affiliation wicri:level="3"><inist:fA14 i1="01"><s1>Nancy-Universtité, Loria, INPL-ENSMN, B.P. 239</s1><s2>54506 Vandœuvre-lès-Nancy</s2><s3>FRA</s3><sZ>1 aut.</sZ><sZ>2 aut.</sZ></inist:fA14><country>France</country><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></author><author><name sortKey="Marion, J Y" sort="Marion, J Y" uniqKey="Marion J" first="J.-Y." last="Marion">J.-Y. Marion</name><affiliation wicri:level="3"><inist:fA14 i1="01"><s1>Nancy-Universtité, Loria, INPL-ENSMN, B.P. 239</s1><s2>54506 Vandœuvre-lès-Nancy</s2><s3>FRA</s3><sZ>1 aut.</sZ><sZ>2 aut.</sZ></inist:fA14><country>France</country><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></author><author><name sortKey="Moyen, J Y" sort="Moyen, J Y" uniqKey="Moyen J" first="J.-Y." last="Moyen">J.-Y. Moyen</name><affiliation wicri:level="4"><inist:fA14 i1="02"><s1>LIPN, Université Paris 13, 99, Avenue J-B Clément</s1><s2>93430 Villetaneuse</s2><s3>FRA</s3><sZ>3 aut.</sZ></inist:fA14><country>France</country><placeName><region type="region" nuts="2">Île-de-France</region><settlement type="city">Villetaneuse</settlement></placeName><orgName type="university">Université Paris 13</orgName></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">INIST</idno><idno type="inist">11-0248946</idno><date when="2011">2011</date><idno type="stanalyst">PASCAL 11-0248946 INIST</idno><idno type="RBID">Pascal:11-0248946</idno><idno type="wicri:Area/PascalFrancis/Corpus">000152</idno><idno type="wicri:Area/PascalFrancis/Curation">000861</idno><idno type="wicri:Area/PascalFrancis/Checkpoint">000124</idno><idno type="wicri:explorRef" wicri:stream="PascalFrancis" wicri:step="Checkpoint">000124</idno><idno type="wicri:doubleKey">0304-3975:2011:Bonfante G:quasi:interpretations:a</idno><idno type="wicri:Area/Main/Merge">002848</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en" level="a">Quasi-interpretations a way to control resources</title><author><name sortKey="Bonfante, G" sort="Bonfante, G" uniqKey="Bonfante G" first="G." last="Bonfante">G. Bonfante</name><affiliation wicri:level="3"><inist:fA14 i1="01"><s1>Nancy-Universtité, Loria, INPL-ENSMN, B.P. 239</s1><s2>54506 Vandœuvre-lès-Nancy</s2><s3>FRA</s3><sZ>1 aut.</sZ><sZ>2 aut.</sZ></inist:fA14><country>France</country><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></author><author><name sortKey="Marion, J Y" sort="Marion, J Y" uniqKey="Marion J" first="J.-Y." last="Marion">J.-Y. Marion</name><affiliation wicri:level="3"><inist:fA14 i1="01"><s1>Nancy-Universtité, Loria, INPL-ENSMN, B.P. 239</s1><s2>54506 Vandœuvre-lès-Nancy</s2><s3>FRA</s3><sZ>1 aut.</sZ><sZ>2 aut.</sZ></inist:fA14><country>France</country><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></author><author><name sortKey="Moyen, J Y" sort="Moyen, J Y" uniqKey="Moyen J" first="J.-Y." last="Moyen">J.-Y. Moyen</name><affiliation wicri:level="4"><inist:fA14 i1="02"><s1>LIPN, Université Paris 13, 99, Avenue J-B Clément</s1><s2>93430 Villetaneuse</s2><s3>FRA</s3><sZ>3 aut.</sZ></inist:fA14><country>France</country><placeName><region type="region" nuts="2">Île-de-France</region><settlement type="city">Villetaneuse</settlement></placeName><orgName type="university">Université Paris 13</orgName></affiliation></author></analytic><series><title level="j" type="main">Theoretical computer science</title><title level="j" type="abbreviated">Theor. comput. sci.</title><idno type="ISSN">0304-3975</idno><imprint><date when="2011">2011</date></imprint></series></biblStruct></sourceDesc><seriesStmt><title level="j" type="main">Theoretical computer science</title><title level="j" type="abbreviated">Theor. comput. sci.</title><idno type="ISSN">0304-3975</idno></seriesStmt></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Assignment</term><term>Complexity</term><term>Complexity class</term><term>Computer theory</term><term>Operational semantics</term><term>Ordering</term><term>Program execution</term><term>Resource</term><term>System analysis</term><term>Termination</term><term>Upper bound</term></keywords><keywords scheme="Pascal" xml:lang="fr"><term>Informatique théorique</term><term>Ressource</term><term>Exécution programme</term><term>Analyse système</term><term>Assignation</term><term>Borne supérieure</term><term>Sémantique opérationnelle</term><term>Borne électrique</term><term>Relation ordre</term><term>Classe complexité</term><term>Complexité</term><term>Analyse complexité</term><term>Sémantique programme</term><term>Operational semantics</term><term>Terminaison</term><term>Terme</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">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 allow the analysis of system complexity. A quasi-interpretation is a numerical assignment, which provides an upper bound on computed functions and which is compatible with the program operational semantics. The quasi-interpretation method offers several advantages: (i) It provides hints in order to optimize an execution, (ii) it gives resource certificates, and (iii) finding quasi-interpretations is decidable for a broad class which is relevant for feasible computations. By combining the quasi-interpretation method with termination tools (here term orderings), we obtained several characterizations of complexity classes starting from PTIME and PSPACE.</div></front></TEI><affiliations><list><country><li>France</li></country><region><li>Grand Est</li><li>Lorraine (région)</li><li>Île-de-France</li></region><settlement><li>Vandœuvre-lès-Nancy</li><li>Villetaneuse</li></settlement><orgName><li>Université Paris 13</li></orgName></list><tree><country name="France"><region name="Grand Est"><name sortKey="Bonfante, G" sort="Bonfante, G" uniqKey="Bonfante G" first="G." last="Bonfante">G. Bonfante</name></region><name sortKey="Marion, J Y" sort="Marion, J Y" uniqKey="Marion J" first="J.-Y." last="Marion">J.-Y. Marion</name><name sortKey="Moyen, J Y" sort="Moyen, J Y" uniqKey="Moyen J" first="J.-Y." last="Moyen">J.-Y. Moyen</name></country></tree></affiliations></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 002848 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Merge/biblio.hfd -nk 002848 | 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é= Pascal:11-0248946
|texte= Quasi-interpretations a way to control resources
}}
| This area was generated with Dilib version V0.6.33. |  |