Real or Natural numbers interpretations and their effect on complexity
Identifieur interne : 003F65 ( Hal/Corpus ); précédent : 003F64; suivant : 003F66Real or Natural numbers interpretations and their effect on complexity
Auteurs : Guillaume Bonfante ; Florian Deloup ; Antoine HenrotSource :
- Theoretical Computer Science [ 0304-3975 ] ; 2015.
English descriptors
Abstract
Interpretation methods have been introduced in the 70’s byLankford in rewriting theory to prove termination. Actually, as shown byBonfante et al., they provide some good tools to prove the complexity ofprograms. However, such an analysis depends deeply on the archimedeanproperty of natural numbers. This is in contradiction with the fact thatfinding an interpretation can be solved by Tarski’s decision procedure(as described by Dershowitz), and consequently interpretations areusually chosen over the reals rather than over the integers. Doing so,one cannot use anymore the (good) properties of the natural(welordering of N used to bound the complexity of programs. We provethat one may benefit from the best of both worlds: the complexityanalysis still holds even with real numbers. The reason lies in a deepalgebraic property of polynomials over the reals. We illustrate this bytwo characterizations, one of polynomial time and one of polynomial space.
Url:
Links to Exploration step
Hal:hal-01093579Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">Real or Natural numbers interpretations and their effect on complexity</title><author><name sortKey="Bonfante, Guillaume" sort="Bonfante, Guillaume" uniqKey="Bonfante G" first="Guillaume" last="Bonfante">Guillaume Bonfante</name><affiliation><hal:affiliation type="researchteam" xml:id="struct-29797" status="VALID"><idno type="RNSR">200918992J</idno><orgName>Theoretical adverse computations, and safety</orgName><orgName type="acronym">CARTE</orgName><desc><address><country key="FR"></country></address><ref type="url">http://www.inria.fr/equipes/carte</ref></desc><listRelation><relation active="#struct-129671" type="direct"></relation><relation active="#struct-300009" type="indirect"></relation><relation active="#struct-423084" type="direct"></relation><relation active="#struct-206040" type="indirect"></relation><relation active="#struct-413289" type="indirect"></relation><relation name="UMR7503" active="#struct-441569" type="indirect"></relation></listRelation><tutelles><tutelle active="#struct-129671" type="direct"><org type="laboratory" xml:id="struct-129671" status="VALID"><idno type="RNSR">198618246Y</idno><orgName>INRIA Nancy - Grand Est</orgName><desc><address><addrLine>615 rue du Jardin Botanique 54600 Villers-lès-Nancy</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/nancy</ref></desc><listRelation><relation active="#struct-300009" type="direct"></relation></listRelation></org></tutelle><tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName><orgName type="acronym">Inria</orgName><desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/en/</ref></desc></org></tutelle><tutelle active="#struct-423084" type="direct"><org type="department" xml:id="struct-423084" status="VALID"><orgName>Department of Formal Methods </orgName><orgName type="acronym">LORIA - FM</orgName><desc><address><country key="FR"></country></address><ref type="url">http://www.loria.fr/la-recherche-en/departements/formal-methods</ref></desc><listRelation><relation active="#struct-206040" type="direct"></relation><relation active="#struct-300009" type="indirect"></relation><relation active="#struct-413289" type="indirect"></relation><relation name="UMR7503" active="#struct-441569" type="indirect"></relation></listRelation></org></tutelle><tutelle active="#struct-206040" type="indirect"><org type="laboratory" xml:id="struct-206040" status="VALID"><idno type="IdRef">067077927</idno><idno type="RNSR">198912571S</idno><idno type="IdUnivLorraine">[UL]RSI--</idno><orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName><orgName type="acronym">LORIA</orgName><date type="start">2012-01-01</date><desc><address><addrLine>Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.loria.fr</ref></desc><listRelation><relation active="#struct-300009" type="direct"></relation><relation active="#struct-413289" type="direct"></relation><relation name="UMR7503" active="#struct-441569" type="direct"></relation></listRelation></org></tutelle><tutelle active="#struct-413289" type="indirect"><org type="institution" xml:id="struct-413289" status="VALID"><idno type="IdRef">157040569</idno><idno type="IdUnivLorraine">[UL]100--</idno><orgName>Université de Lorraine</orgName><orgName type="acronym">UL</orgName><date type="start">2012-01-01</date><desc><address><addrLine>34 cours Léopold - CS 25233 - 54052 Nancy cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.univ-lorraine.fr/</ref></desc></org></tutelle><tutelle name="UMR7503" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno><idno type="IdRef">02636817X</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle></tutelles></hal:affiliation></affiliation></author><author><name sortKey="Deloup, Florian" sort="Deloup, Florian" uniqKey="Deloup F" first="Florian" last="Deloup">Florian Deloup</name><affiliation><hal:affiliation type="laboratory" xml:id="struct-1954" status="VALID"><orgName>Institut de Mathématiques de Toulouse UMR5219</orgName><orgName type="acronym">IMT</orgName><desc><address><addrLine>UPS IMT, F-31062 Toulouse Cedex 9, France INSA, F-31077 Toulouse, France UT1, F-31042 Toulouse, France UT2, F-31058 Toulouse, France</addrLine><country key="FR"></country></address><ref type="url">https://www.math.univ-toulouse.fr/</ref></desc><listRelation><relation active="#struct-81148" type="direct"></relation><relation active="#struct-116256" type="direct"></relation><relation active="#struct-217752" type="direct"></relation><relation active="#struct-301089" type="direct"></relation><relation active="#struct-413500" type="direct"></relation><relation active="#struct-441569" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-81148" type="direct"><org type="institution" xml:id="struct-81148" status="VALID"><orgName>Université Toulouse 1 Capitole</orgName><orgName type="acronym">UT1</orgName><desc><address><addrLine>2 rue du Doyen-Gabriel-Marty - 31042 Toulouse Cedex 9 </addrLine><country key="FR"></country></address><ref type="url">http://www.ut-capitole.fr/</ref></desc></org></tutelle><tutelle active="#struct-116256" type="direct"><org type="institution" xml:id="struct-116256" status="VALID"><idno type="IdRef">026403994</idno><orgName>Université Toulouse 2</orgName><orgName type="acronym">UT2</orgName><date type="start">1971-01-01</date><desc><address><addrLine>5 allées Antonio Machado - 31058 Toulouse Cedex 9 </addrLine><country key="FR"></country></address><ref type="url">http://www.univ-tlse2.fr</ref></desc></org></tutelle><tutelle active="#struct-217752" type="direct"><org type="institution" xml:id="struct-217752" status="VALID"><orgName>Université Paul Sabatier - Toulouse 3</orgName><orgName type="acronym">UPS</orgName><desc><address><addrLine>118 route de Narbonne - 31062 Toulouse</addrLine><country key="FR"></country></address><ref type="url">http://www.univ-tlse3.fr/</ref></desc></org></tutelle><tutelle active="#struct-301089" type="direct"><org type="institution" xml:id="struct-301089" status="VALID"><orgName>PRES Université de Toulouse</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-413500" type="direct"><org type="institution" xml:id="struct-413500" status="INCOMING"><orgName>Institut National des Sciences Appliquées de Toulouse</orgName><orgName type="acronym">INSA de Toulouse</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-441569" type="direct"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno><idno type="IdRef">02636817X</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle></tutelles></hal:affiliation></affiliation></author><author><name sortKey="Henrot, Antoine" sort="Henrot, Antoine" uniqKey="Henrot A" first="Antoine" last="Henrot">Antoine Henrot</name><affiliation><hal:affiliation type="researchteam" xml:id="struct-388636" status="VALID"><orgName>Equations aux dérivées partielles</orgName><orgName type="acronym">EDP</orgName><desc><address><country key="FR"></country></address><ref type="url">http://iecl.univ-lorraine.fr/equipesIECL_edp.html</ref></desc><listRelation><relation active="#struct-211251" type="direct"></relation><relation active="#struct-413289" type="indirect"></relation><relation name="UMR7502" active="#struct-441569" type="indirect"></relation></listRelation><tutelles><tutelle active="#struct-211251" type="direct"><org type="laboratory" xml:id="struct-211251" status="VALID"><idno type="IdRef">180064606</idno><idno type="RNSR">199712570F</idno><idno type="IdUnivLorraine">[UL]RSB--</idno><orgName>Institut Élie Cartan de Lorraine</orgName><orgName type="acronym">IECL</orgName><date type="start">2012-01-01</date><desc><address><addrLine>Université de Lorraine, Boulevard des Aiguillettes BP 70239 54506 Vandoeuvre-les-Nancy CedexIle du Saulcy - 57 045 Metz Cedex 01</addrLine><country key="FR"></country></address><ref type="url">http://iecl.univ-lorraine.fr/</ref></desc><listRelation><relation active="#struct-413289" type="direct"></relation><relation name="UMR7502" active="#struct-441569" type="direct"></relation></listRelation></org></tutelle><tutelle active="#struct-413289" type="indirect"><org type="institution" xml:id="struct-413289" status="VALID"><idno type="IdRef">157040569</idno><idno type="IdUnivLorraine">[UL]100--</idno><orgName>Université de Lorraine</orgName><orgName type="acronym">UL</orgName><date type="start">2012-01-01</date><desc><address><addrLine>34 cours Léopold - CS 25233 - 54052 Nancy cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.univ-lorraine.fr/</ref></desc></org></tutelle><tutelle name="UMR7502" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno><idno type="IdRef">02636817X</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle></tutelles></hal:affiliation></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">HAL</idno><idno type="RBID">Hal:hal-01093579</idno><idno type="halId">hal-01093579</idno><idno type="halUri">https://hal.archives-ouvertes.fr/hal-01093579</idno><idno type="url">https://hal.archives-ouvertes.fr/hal-01093579</idno><date when="2015">2015</date><idno type="wicri:Area/Hal/Corpus">003F65</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en">Real or Natural numbers interpretations and their effect on complexity</title><author><name sortKey="Bonfante, Guillaume" sort="Bonfante, Guillaume" uniqKey="Bonfante G" first="Guillaume" last="Bonfante">Guillaume Bonfante</name><affiliation><hal:affiliation type="researchteam" xml:id="struct-29797" status="VALID"><idno type="RNSR">200918992J</idno><orgName>Theoretical adverse computations, and safety</orgName><orgName type="acronym">CARTE</orgName><desc><address><country key="FR"></country></address><ref type="url">http://www.inria.fr/equipes/carte</ref></desc><listRelation><relation active="#struct-129671" type="direct"></relation><relation active="#struct-300009" type="indirect"></relation><relation active="#struct-423084" type="direct"></relation><relation active="#struct-206040" type="indirect"></relation><relation active="#struct-413289" type="indirect"></relation><relation name="UMR7503" active="#struct-441569" type="indirect"></relation></listRelation><tutelles><tutelle active="#struct-129671" type="direct"><org type="laboratory" xml:id="struct-129671" status="VALID"><idno type="RNSR">198618246Y</idno><orgName>INRIA Nancy - Grand Est</orgName><desc><address><addrLine>615 rue du Jardin Botanique 54600 Villers-lès-Nancy</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/nancy</ref></desc><listRelation><relation active="#struct-300009" type="direct"></relation></listRelation></org></tutelle><tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName><orgName type="acronym">Inria</orgName><desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/en/</ref></desc></org></tutelle><tutelle active="#struct-423084" type="direct"><org type="department" xml:id="struct-423084" status="VALID"><orgName>Department of Formal Methods </orgName><orgName type="acronym">LORIA - FM</orgName><desc><address><country key="FR"></country></address><ref type="url">http://www.loria.fr/la-recherche-en/departements/formal-methods</ref></desc><listRelation><relation active="#struct-206040" type="direct"></relation><relation active="#struct-300009" type="indirect"></relation><relation active="#struct-413289" type="indirect"></relation><relation name="UMR7503" active="#struct-441569" type="indirect"></relation></listRelation></org></tutelle><tutelle active="#struct-206040" type="indirect"><org type="laboratory" xml:id="struct-206040" status="VALID"><idno type="IdRef">067077927</idno><idno type="RNSR">198912571S</idno><idno type="IdUnivLorraine">[UL]RSI--</idno><orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName><orgName type="acronym">LORIA</orgName><date type="start">2012-01-01</date><desc><address><addrLine>Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.loria.fr</ref></desc><listRelation><relation active="#struct-300009" type="direct"></relation><relation active="#struct-413289" type="direct"></relation><relation name="UMR7503" active="#struct-441569" type="direct"></relation></listRelation></org></tutelle><tutelle active="#struct-413289" type="indirect"><org type="institution" xml:id="struct-413289" status="VALID"><idno type="IdRef">157040569</idno><idno type="IdUnivLorraine">[UL]100--</idno><orgName>Université de Lorraine</orgName><orgName type="acronym">UL</orgName><date type="start">2012-01-01</date><desc><address><addrLine>34 cours Léopold - CS 25233 - 54052 Nancy cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.univ-lorraine.fr/</ref></desc></org></tutelle><tutelle name="UMR7503" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno><idno type="IdRef">02636817X</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle></tutelles></hal:affiliation></affiliation></author><author><name sortKey="Deloup, Florian" sort="Deloup, Florian" uniqKey="Deloup F" first="Florian" last="Deloup">Florian Deloup</name><affiliation><hal:affiliation type="laboratory" xml:id="struct-1954" status="VALID"><orgName>Institut de Mathématiques de Toulouse UMR5219</orgName><orgName type="acronym">IMT</orgName><desc><address><addrLine>UPS IMT, F-31062 Toulouse Cedex 9, France INSA, F-31077 Toulouse, France UT1, F-31042 Toulouse, France UT2, F-31058 Toulouse, France</addrLine><country key="FR"></country></address><ref type="url">https://www.math.univ-toulouse.fr/</ref></desc><listRelation><relation active="#struct-81148" type="direct"></relation><relation active="#struct-116256" type="direct"></relation><relation active="#struct-217752" type="direct"></relation><relation active="#struct-301089" type="direct"></relation><relation active="#struct-413500" type="direct"></relation><relation active="#struct-441569" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-81148" type="direct"><org type="institution" xml:id="struct-81148" status="VALID"><orgName>Université Toulouse 1 Capitole</orgName><orgName type="acronym">UT1</orgName><desc><address><addrLine>2 rue du Doyen-Gabriel-Marty - 31042 Toulouse Cedex 9 </addrLine><country key="FR"></country></address><ref type="url">http://www.ut-capitole.fr/</ref></desc></org></tutelle><tutelle active="#struct-116256" type="direct"><org type="institution" xml:id="struct-116256" status="VALID"><idno type="IdRef">026403994</idno><orgName>Université Toulouse 2</orgName><orgName type="acronym">UT2</orgName><date type="start">1971-01-01</date><desc><address><addrLine>5 allées Antonio Machado - 31058 Toulouse Cedex 9 </addrLine><country key="FR"></country></address><ref type="url">http://www.univ-tlse2.fr</ref></desc></org></tutelle><tutelle active="#struct-217752" type="direct"><org type="institution" xml:id="struct-217752" status="VALID"><orgName>Université Paul Sabatier - Toulouse 3</orgName><orgName type="acronym">UPS</orgName><desc><address><addrLine>118 route de Narbonne - 31062 Toulouse</addrLine><country key="FR"></country></address><ref type="url">http://www.univ-tlse3.fr/</ref></desc></org></tutelle><tutelle active="#struct-301089" type="direct"><org type="institution" xml:id="struct-301089" status="VALID"><orgName>PRES Université de Toulouse</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-413500" type="direct"><org type="institution" xml:id="struct-413500" status="INCOMING"><orgName>Institut National des Sciences Appliquées de Toulouse</orgName><orgName type="acronym">INSA de Toulouse</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-441569" type="direct"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno><idno type="IdRef">02636817X</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle></tutelles></hal:affiliation></affiliation></author><author><name sortKey="Henrot, Antoine" sort="Henrot, Antoine" uniqKey="Henrot A" first="Antoine" last="Henrot">Antoine Henrot</name><affiliation><hal:affiliation type="researchteam" xml:id="struct-388636" status="VALID"><orgName>Equations aux dérivées partielles</orgName><orgName type="acronym">EDP</orgName><desc><address><country key="FR"></country></address><ref type="url">http://iecl.univ-lorraine.fr/equipesIECL_edp.html</ref></desc><listRelation><relation active="#struct-211251" type="direct"></relation><relation active="#struct-413289" type="indirect"></relation><relation name="UMR7502" active="#struct-441569" type="indirect"></relation></listRelation><tutelles><tutelle active="#struct-211251" type="direct"><org type="laboratory" xml:id="struct-211251" status="VALID"><idno type="IdRef">180064606</idno><idno type="RNSR">199712570F</idno><idno type="IdUnivLorraine">[UL]RSB--</idno><orgName>Institut Élie Cartan de Lorraine</orgName><orgName type="acronym">IECL</orgName><date type="start">2012-01-01</date><desc><address><addrLine>Université de Lorraine, Boulevard des Aiguillettes BP 70239 54506 Vandoeuvre-les-Nancy CedexIle du Saulcy - 57 045 Metz Cedex 01</addrLine><country key="FR"></country></address><ref type="url">http://iecl.univ-lorraine.fr/</ref></desc><listRelation><relation active="#struct-413289" type="direct"></relation><relation name="UMR7502" active="#struct-441569" type="direct"></relation></listRelation></org></tutelle><tutelle active="#struct-413289" type="indirect"><org type="institution" xml:id="struct-413289" status="VALID"><idno type="IdRef">157040569</idno><idno type="IdUnivLorraine">[UL]100--</idno><orgName>Université de Lorraine</orgName><orgName type="acronym">UL</orgName><date type="start">2012-01-01</date><desc><address><addrLine>34 cours Léopold - CS 25233 - 54052 Nancy cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.univ-lorraine.fr/</ref></desc></org></tutelle><tutelle name="UMR7502" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno><idno type="IdRef">02636817X</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle></tutelles></hal:affiliation></affiliation></author></analytic><series><title level="j">Theoretical Computer Science</title><idno type="ISSN">0304-3975</idno><imprint><date type="datePub">2015</date></imprint></series></biblStruct></sourceDesc></fileDesc><profileDesc><textClass><keywords scheme="mix" xml:lang="en"><term>Algebraic Geometry</term><term>Complexity Theory</term><term>Interpretation</term><term>Polynomial Time</term><term>rewriting</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Interpretation methods have been introduced in the 70’s byLankford in rewriting theory to prove termination. Actually, as shown byBonfante et al., they provide some good tools to prove the complexity ofprograms. However, such an analysis depends deeply on the archimedeanproperty of natural numbers. This is in contradiction with the fact thatfinding an interpretation can be solved by Tarski’s decision procedure(as described by Dershowitz), and consequently interpretations areusually chosen over the reals rather than over the integers. Doing so,one cannot use anymore the (good) properties of the natural(welordering of N used to bound the complexity of programs. We provethat one may benefit from the best of both worlds: the complexityanalysis still holds even with real numbers. The reason lies in a deepalgebraic property of polynomials over the reals. We illustrate this bytwo characterizations, one of polynomial time and one of polynomial space.</div></front></TEI><hal api="V3"><titleStmt><title xml:lang="en">Real or Natural numbers interpretations and their effect on complexity</title><author role="aut"><persName><forename type="first">Guillaume</forename><surname>Bonfante</surname></persName><email>Guillaume.Bonfante@loria.fr</email><idno type="halauthor">66157</idno><affiliation ref="#struct-29797"></affiliation></author><author role="aut"><persName><forename type="first">Florian</forename><surname>Deloup</surname></persName><email>deloup@math.univ-toulouse.fr</email><idno type="halauthor">648277</idno><affiliation ref="#struct-1954"></affiliation></author><author role="aut"><persName><forename type="first">Antoine</forename><surname>Henrot</surname></persName><email></email><idno type="halauthor">100977</idno><affiliation ref="#struct-388636"></affiliation></author><editor role="depositor"><persName><forename>Antoine</forename><surname>Henrot</surname></persName><email>Antoine.Henrot@univ-lorraine.fr</email></editor></titleStmt><editionStmt><edition n="v1" type="current"><date type="whenSubmitted">2014-12-10 18:05:55</date><date type="whenModified">2016-02-21 18:51:24</date><date type="whenReleased">2014-12-10 18:05:55</date><date type="whenProduced">2015</date></edition><respStmt><resp>contributor</resp><name key="104015"><persName><forename>Antoine</forename><surname>Henrot</surname></persName><email>Antoine.Henrot@univ-lorraine.fr</email></name></respStmt></editionStmt><publicationStmt><distributor>CCSD</distributor><idno type="halId">hal-01093579</idno><idno type="halUri">https://hal.archives-ouvertes.fr/hal-01093579</idno><idno type="halBibtex">bonfante:hal-01093579</idno><idno type="halRefHtml">Theoretical Computer Science, Elsevier, 2015, pp.23</idno><idno type="halRef">Theoretical Computer Science, Elsevier, 2015, pp.23</idno></publicationStmt><seriesStmt><idno type="stamp" n="CNRS">CNRS - Centre national de la recherche scientifique</idno><idno type="stamp" n="INRIA">INRIA - Institut National de Recherche en Informatique et en Automatique</idno><idno type="stamp" n="IECN">IECN - Institut Elie Cartan Nancy</idno><idno type="stamp" n="INRIA-LORRAINE">INRIA Nancy - Grand Est</idno><idno type="stamp" n="LORIA2">Publications du LORIA</idno><idno type="stamp" n="INRIA-NANCY-GRAND-EST">INRIA Nancy - Grand Est</idno><idno type="stamp" n="LORIA-FM" p="LORIA">Méthodes formelles</idno><idno type="stamp" n="UNIV-LORRAINE">Université de Lorraine</idno><idno type="stamp" n="LORIA">LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications</idno><idno type="stamp" n="INRIA_TEST">INRIA - Institut National de Recherche en Informatique et en Automatique</idno><idno type="stamp" n="IMT">Institut de Mathématiques de Toulouse</idno><idno type="stamp" n="INSA-TOULOUSE">Institut National des Sciences Appliquées de Toulouse</idno><idno type="stamp" n="UNIV-TLSE2">Université Toulouse 2</idno><idno type="stamp" n="INRIA2">INRIA 2</idno><idno type="stamp" n="UNIV-TLSE3">Université Paul Sabatier - Toulouse III</idno></seriesStmt><notesStmt><note type="audience" n="2">International</note><note type="popular" n="0">No</note><note type="peer" n="1">Yes</note></notesStmt><sourceDesc><biblStruct><analytic><title xml:lang="en">Real or Natural numbers interpretations and their effect on complexity</title><author role="aut"><persName><forename type="first">Guillaume</forename><surname>Bonfante</surname></persName><email>Guillaume.Bonfante@loria.fr</email><idno type="halAuthorId">66157</idno><affiliation ref="#struct-29797"></affiliation></author><author role="aut"><persName><forename type="first">Florian</forename><surname>Deloup</surname></persName><email>deloup@math.univ-toulouse.fr</email><idno type="halAuthorId">648277</idno><affiliation ref="#struct-1954"></affiliation></author><author role="aut"><persName><forename type="first">Antoine</forename><surname>Henrot</surname></persName><idno type="halAuthorId">100977</idno><affiliation ref="#struct-388636"></affiliation></author></analytic><monogr><idno type="halJournalId" status="VALID">19594</idno><idno type="issn">0304-3975</idno><title level="j">Theoretical Computer Science</title><imprint><publisher>Elsevier</publisher><biblScope unit="pp">23</biblScope><date type="datePub">2015</date></imprint></monogr></biblStruct></sourceDesc><profileDesc><langUsage><language ident="en">English</language></langUsage><textClass><keywords scheme="author"><term xml:lang="en">Polynomial Time</term><term xml:lang="en">Complexity Theory</term><term xml:lang="en">Algebraic Geometry</term><term xml:lang="en">Interpretation</term><term xml:lang="en">rewriting</term></keywords><classCode scheme="halDomain" n="info.info-cc">Computer Science [cs]/Computational Complexity [cs.CC]</classCode><classCode scheme="halTypology" n="ART">Journal articles</classCode></textClass><abstract xml:lang="en">Interpretation methods have been introduced in the 70’s byLankford in rewriting theory to prove termination. Actually, as shown byBonfante et al., they provide some good tools to prove the complexity ofprograms. However, such an analysis depends deeply on the archimedeanproperty of natural numbers. This is in contradiction with the fact thatfinding an interpretation can be solved by Tarski’s decision procedure(as described by Dershowitz), and consequently interpretations areusually chosen over the reals rather than over the integers. Doing so,one cannot use anymore the (good) properties of the natural(welordering of N used to bound the complexity of programs. We provethat one may benefit from the best of both worlds: the complexityanalysis still holds even with real numbers. The reason lies in a deepalgebraic property of polynomials over the reals. We illustrate this bytwo characterizations, one of polynomial time and one of polynomial space.</abstract></profileDesc></hal></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Hal/Corpus
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 003F65 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Hal/Corpus/biblio.hfd -nk 003F65 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Hal
|étape= Corpus
|type= RBID
|clé= Hal:hal-01093579
|texte= Real or Natural numbers interpretations and their effect on complexity
}}
| This area was generated with Dilib version V0.6.33. |  |