Quasi-interpretations and small space bounds
Identifieur interne : 006599 ( Main/Merge ); précédent : 006598; suivant : 006600Quasi-interpretations and small space bounds
Auteurs : Guillaume Bonfante [France] ; Jean-Yves Marion [France] ; Jean-Yves Moyen [France]Source :
- Lecture notes in computer science [ 0302-9743 ] ; 2005.
Descripteurs français
- Pascal (Inist)
English descriptors
- KwdEn :
Abstract
Quasi-interpretations are an useful tool to control resources usage of term rewriting systems, either time or space. They not only combine well with path orderings and provide characterizations of usual complexity classes but also give hints in order to optimize the program. Moreover, the existence of a quasi-interpretation is decidable. In this paper, we present some more characterizations of complexity classes using quasi-interpretations. We mainly focus on small spacebounded complexity classes. On one hand, by restricting quasi-interpretations to sums (that is allowing only affine quasi-interpretations), we obtain a characterization of LINSPACE. On the other hand, a strong tiering discipline on programs together with quasi-interpretations yield a characterization of LOG SPACE. Lastly, we give two new characterizations of PSPACE: in the first, the quasi-interpretation has to be strictly decreasing on each rule and in the second, some linearity constraints are added to the system but no assumption concerning the termination proof is made.
Links toward previous steps (curation, corpus...)
- to stream PascalFrancis, to step Corpus: 000562
- to stream PascalFrancis, to step Curation: 000476
- to stream PascalFrancis, to step Checkpoint: 000462
Links to Exploration step
Pascal:05-0287093Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" level="a">Quasi-interpretations and small space bounds</title><author><name sortKey="Bonfante, Guillaume" sort="Bonfante, Guillaume" uniqKey="Bonfante G" first="Guillaume" last="Bonfante">Guillaume Bonfante</name><affiliation wicri:level="3"><inist:fA14 i1="01"><s1>Loria, Calligramme project, B.P. 239</s1><s2>54506 Vandœuvre-lès-Nancy</s2><s3>FRA</s3><sZ>1 aut.</sZ><sZ>2 aut.</sZ><sZ>3 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><affiliation wicri:level="4"><inist:fA14 i1="02"><s1>École Nationale Supérieure des Mines de Nancy, INPL</s1><s3>FRA</s3><sZ>1 aut.</sZ><sZ>2 aut.</sZ></inist:fA14><country>France</country><wicri:noRegion>INPL</wicri:noRegion><placeName><settlement type="city">Nancy</settlement><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region></placeName><orgName type="university">Institut national polytechnique de Lorraine</orgName><orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName></affiliation></author><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"><inist:fA14 i1="01"><s1>Loria, Calligramme project, B.P. 239</s1><s2>54506 Vandœuvre-lès-Nancy</s2><s3>FRA</s3><sZ>1 aut.</sZ><sZ>2 aut.</sZ><sZ>3 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><affiliation wicri:level="4"><inist:fA14 i1="02"><s1>École Nationale Supérieure des Mines de Nancy, INPL</s1><s3>FRA</s3><sZ>1 aut.</sZ><sZ>2 aut.</sZ></inist:fA14><country>France</country><wicri:noRegion>INPL</wicri:noRegion><placeName><settlement type="city">Nancy</settlement><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region></placeName><orgName type="university">Institut national polytechnique de Lorraine</orgName><orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName></affiliation></author><author><name sortKey="Moyen, Jean Yves" sort="Moyen, Jean Yves" uniqKey="Moyen J" first="Jean-Yves" last="Moyen">Jean-Yves Moyen</name><affiliation wicri:level="3"><inist:fA14 i1="01"><s1>Loria, Calligramme project, B.P. 239</s1><s2>54506 Vandœuvre-lès-Nancy</s2><s3>FRA</s3><sZ>1 aut.</sZ><sZ>2 aut.</sZ><sZ>3 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><affiliation wicri:level="1"><inist:fA14 i1="03"><s1>Université Henri Poincaré Nancy I</s1><s3>FRA</s3><sZ>3 aut.</sZ></inist:fA14><country>France</country><wicri:noRegion>Université Henri Poincaré Nancy I</wicri:noRegion><wicri:noRegion>Université Henri Poincaré Nancy I</wicri:noRegion></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">INIST</idno><idno type="inist">05-0287093</idno><date when="2005">2005</date><idno type="stanalyst">PASCAL 05-0287093 INIST</idno><idno type="RBID">Pascal:05-0287093</idno><idno type="wicri:Area/PascalFrancis/Corpus">000562</idno><idno type="wicri:Area/PascalFrancis/Curation">000476</idno><idno type="wicri:Area/PascalFrancis/Checkpoint">000462</idno><idno type="wicri:explorRef" wicri:stream="PascalFrancis" wicri:step="Checkpoint">000462</idno><idno type="wicri:doubleKey">0302-9743:2005:Bonfante G:quasi:interpretations:and</idno><idno type="wicri:Area/Main/Merge">006599</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en" level="a">Quasi-interpretations and small space bounds</title><author><name sortKey="Bonfante, Guillaume" sort="Bonfante, Guillaume" uniqKey="Bonfante G" first="Guillaume" last="Bonfante">Guillaume Bonfante</name><affiliation wicri:level="3"><inist:fA14 i1="01"><s1>Loria, Calligramme project, B.P. 239</s1><s2>54506 Vandœuvre-lès-Nancy</s2><s3>FRA</s3><sZ>1 aut.</sZ><sZ>2 aut.</sZ><sZ>3 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><affiliation wicri:level="4"><inist:fA14 i1="02"><s1>École Nationale Supérieure des Mines de Nancy, INPL</s1><s3>FRA</s3><sZ>1 aut.</sZ><sZ>2 aut.</sZ></inist:fA14><country>France</country><wicri:noRegion>INPL</wicri:noRegion><placeName><settlement type="city">Nancy</settlement><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region></placeName><orgName type="university">Institut national polytechnique de Lorraine</orgName><orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName></affiliation></author><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"><inist:fA14 i1="01"><s1>Loria, Calligramme project, B.P. 239</s1><s2>54506 Vandœuvre-lès-Nancy</s2><s3>FRA</s3><sZ>1 aut.</sZ><sZ>2 aut.</sZ><sZ>3 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><affiliation wicri:level="4"><inist:fA14 i1="02"><s1>École Nationale Supérieure des Mines de Nancy, INPL</s1><s3>FRA</s3><sZ>1 aut.</sZ><sZ>2 aut.</sZ></inist:fA14><country>France</country><wicri:noRegion>INPL</wicri:noRegion><placeName><settlement type="city">Nancy</settlement><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region></placeName><orgName type="university">Institut national polytechnique de Lorraine</orgName><orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName></affiliation></author><author><name sortKey="Moyen, Jean Yves" sort="Moyen, Jean Yves" uniqKey="Moyen J" first="Jean-Yves" last="Moyen">Jean-Yves Moyen</name><affiliation wicri:level="3"><inist:fA14 i1="01"><s1>Loria, Calligramme project, B.P. 239</s1><s2>54506 Vandœuvre-lès-Nancy</s2><s3>FRA</s3><sZ>1 aut.</sZ><sZ>2 aut.</sZ><sZ>3 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><affiliation wicri:level="1"><inist:fA14 i1="03"><s1>Université Henri Poincaré Nancy I</s1><s3>FRA</s3><sZ>3 aut.</sZ></inist:fA14><country>France</country><wicri:noRegion>Université Henri Poincaré Nancy I</wicri:noRegion><wicri:noRegion>Université Henri Poincaré Nancy I</wicri:noRegion></affiliation></author></analytic><series><title level="j" type="main">Lecture notes in computer science</title><idno type="ISSN">0302-9743</idno><imprint><date when="2005">2005</date></imprint></series></biblStruct></sourceDesc><seriesStmt><title level="j" type="main">Lecture notes in computer science</title><idno type="ISSN">0302-9743</idno></seriesStmt></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Complexity class</term><term>Decidability</term><term>Linearity</term><term>Ordering</term><term>Resource management</term><term>Rewriting</term><term>Rewriting systems</term><term>Termination problem</term></keywords><keywords scheme="Pascal" xml:lang="fr"><term>Gestion ressources</term><term>Système réécriture</term><term>Relation ordre</term><term>Classe complexité</term><term>Décidabilité</term><term>Linéarité</term><term>Problème terminaison</term><term>Réécriture</term><term>.</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Quasi-interpretations are an useful tool to control resources usage of term rewriting systems, either time or space. They not only combine well with path orderings and provide characterizations of usual complexity classes but also give hints in order to optimize the program. Moreover, the existence of a quasi-interpretation is decidable. In this paper, we present some more characterizations of complexity classes using quasi-interpretations. We mainly focus on small spacebounded complexity classes. On one hand, by restricting quasi-interpretations to sums (that is allowing only affine quasi-interpretations), we obtain a characterization of LINSPACE. On the other hand, a strong tiering discipline on programs together with quasi-interpretations yield a characterization of LOG SPACE. Lastly, we give two new characterizations of PSPACE: in the first, the quasi-interpretation has to be strictly decreasing on each rule and in the second, some linearity constraints are added to the system but no assumption concerning the termination proof is made.</div></front></TEI><affiliations><list><country><li>France</li></country><region><li>Grand Est</li><li>Lorraine (région)</li></region><settlement><li>Nancy</li><li>Vandœuvre-lès-Nancy</li></settlement><orgName><li>Institut national polytechnique de Lorraine</li><li>Université de Lorraine</li></orgName></list><tree><country name="France"><region name="Grand Est"><name sortKey="Bonfante, Guillaume" sort="Bonfante, Guillaume" uniqKey="Bonfante G" first="Guillaume" last="Bonfante">Guillaume Bonfante</name></region><name sortKey="Bonfante, Guillaume" sort="Bonfante, Guillaume" uniqKey="Bonfante G" first="Guillaume" last="Bonfante">Guillaume Bonfante</name><name sortKey="Marion, Jean Yves" sort="Marion, Jean Yves" uniqKey="Marion J" first="Jean-Yves" last="Marion">Jean-Yves Marion</name><name sortKey="Marion, Jean Yves" sort="Marion, Jean Yves" uniqKey="Marion J" first="Jean-Yves" last="Marion">Jean-Yves Marion</name><name sortKey="Moyen, Jean Yves" sort="Moyen, Jean Yves" uniqKey="Moyen J" first="Jean-Yves" last="Moyen">Jean-Yves Moyen</name><name sortKey="Moyen, Jean Yves" sort="Moyen, Jean Yves" uniqKey="Moyen J" first="Jean-Yves" last="Moyen">Jean-Yves 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 006599 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Merge/biblio.hfd -nk 006599 | 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:05-0287093
|texte= Quasi-interpretations and small space bounds
}}
| This area was generated with Dilib version V0.6.33. |  |