Complexity classes and rewrite systems with polynomial interpretation
Identifieur interne : 001699 ( Hal/Corpus ); précédent : 001698; suivant : 001700Complexity classes and rewrite systems with polynomial interpretation
Auteurs : Guillaume Bonfante ; Adam Cichon ; Jean-Yves Marion ; Hélène TouzetSource :
Descripteurs français
- mix :
Abstract
Les systèmes de réécriture munis d'une interprétation polynomiale ont la propriété de terminaison forte. En fait, et a priori, ainsi que le font remarquer Huet et Oppen, on peut supposer que de telles interprétations sont un bon candidat pour l'étude des fonctions dont la complexité est faible. Ainsi, Cichon et Lescanne ont calculé des bornes de complexité de fonctions unaires selon le type d'interpétation du successeur. Nous nous intéressons plus particulièrement aux fonctions sur les mots qui sont calculables par des systèmes de réécriture munis d'une interprétation polynomiale. Nous les classifions selon un critère basé sur la forme de l'interprétation des constructeurs. Ceci nous conduit à la définition de trois classes qui s'avèrent être exactement : la classe des fonctions calculables en temps polynomial, en temps linéairement exponentiel et en temps doublement exponentiel. d'autre part, nous donnons une caractérisation de l'espace linéaire.
Url:
Links to Exploration step
Hal:inria-00098689Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">Complexity classes and rewrite systems with polynomial interpretation</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-2347" status="OLD"><idno type="RNSR">199618306V</idno>
<orgName>Linear logic, proof networks and categorial grammars</orgName>
<orgName type="acronym">CALLIGRAMME</orgName>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/equipes/calligramme</ref>
</desc>
<listRelation><relation active="#struct-160" type="direct"></relation>
<relation name="UMR7503" active="#struct-441569" type="indirect"></relation>
<relation active="#struct-300009" type="indirect"></relation>
<relation active="#struct-300291" type="indirect"></relation>
<relation active="#struct-300292" type="indirect"></relation>
<relation active="#struct-300293" type="indirect"></relation>
<relation active="#struct-2496" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-160" type="direct"><org type="laboratory" xml:id="struct-160" status="OLD"><orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName>
<orgName type="acronym">LORIA</orgName>
<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 name="UMR7503" active="#struct-441569" type="direct"></relation>
<relation active="#struct-300009" type="direct"></relation>
<relation active="#struct-300291" type="direct"></relation>
<relation active="#struct-300292" type="direct"></relation>
<relation active="#struct-300293" type="direct"></relation>
</listRelation>
</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>
<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-300291" type="indirect"><org type="institution" xml:id="struct-300291" status="OLD"><orgName>Université Henri Poincaré - Nancy 1</orgName>
<orgName type="acronym">UHP</orgName>
<date type="end">2011-12-31</date>
<desc><address><addrLine>24-30 rue Lionnois, BP 60120, 54 003 NANCY cedex, France</addrLine>
<country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300292" type="indirect"><org type="institution" xml:id="struct-300292" status="OLD"><orgName>Université Nancy 2</orgName>
<date type="end">2011-12-31</date>
<desc><address><addrLine>91 avenue de la Libération, BP 454, 54001 Nancy cedex</addrLine>
<country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300293" type="indirect"><org type="institution" xml:id="struct-300293" status="OLD"><orgName>Institut National Polytechnique de Lorraine</orgName>
<orgName type="acronym">INPL</orgName>
<date type="end">2011-12-31</date>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle active="#struct-2496" type="direct"><org type="laboratory" xml:id="struct-2496" status="OLD"><orgName>INRIA Lorraine</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/centre-de-recherche-inria/nancy-grand-est</ref>
</desc>
<listRelation><relation active="#struct-300009" type="direct"></relation>
</listRelation>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
</affiliation>
</author>
<author><name sortKey="Cichon, Adam" sort="Cichon, Adam" uniqKey="Cichon A" first="Adam" last="Cichon">Adam Cichon</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="Touzet, Helene" sort="Touzet, Helene" uniqKey="Touzet H" first="Hélène" last="Touzet">Hélène Touzet</name>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">HAL</idno>
<idno type="RBID">Hal:inria-00098689</idno>
<idno type="halId">inria-00098689</idno>
<idno type="halUri">https://hal.inria.fr/inria-00098689</idno>
<idno type="url">https://hal.inria.fr/inria-00098689</idno>
<date when="1998">1998</date>
<idno type="wicri:Area/Hal/Corpus">001699</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en">Complexity classes and rewrite systems with polynomial interpretation</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-2347" status="OLD"><idno type="RNSR">199618306V</idno>
<orgName>Linear logic, proof networks and categorial grammars</orgName>
<orgName type="acronym">CALLIGRAMME</orgName>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/equipes/calligramme</ref>
</desc>
<listRelation><relation active="#struct-160" type="direct"></relation>
<relation name="UMR7503" active="#struct-441569" type="indirect"></relation>
<relation active="#struct-300009" type="indirect"></relation>
<relation active="#struct-300291" type="indirect"></relation>
<relation active="#struct-300292" type="indirect"></relation>
<relation active="#struct-300293" type="indirect"></relation>
<relation active="#struct-2496" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-160" type="direct"><org type="laboratory" xml:id="struct-160" status="OLD"><orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName>
<orgName type="acronym">LORIA</orgName>
<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 name="UMR7503" active="#struct-441569" type="direct"></relation>
<relation active="#struct-300009" type="direct"></relation>
<relation active="#struct-300291" type="direct"></relation>
<relation active="#struct-300292" type="direct"></relation>
<relation active="#struct-300293" type="direct"></relation>
</listRelation>
</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>
<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-300291" type="indirect"><org type="institution" xml:id="struct-300291" status="OLD"><orgName>Université Henri Poincaré - Nancy 1</orgName>
<orgName type="acronym">UHP</orgName>
<date type="end">2011-12-31</date>
<desc><address><addrLine>24-30 rue Lionnois, BP 60120, 54 003 NANCY cedex, France</addrLine>
<country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300292" type="indirect"><org type="institution" xml:id="struct-300292" status="OLD"><orgName>Université Nancy 2</orgName>
<date type="end">2011-12-31</date>
<desc><address><addrLine>91 avenue de la Libération, BP 454, 54001 Nancy cedex</addrLine>
<country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300293" type="indirect"><org type="institution" xml:id="struct-300293" status="OLD"><orgName>Institut National Polytechnique de Lorraine</orgName>
<orgName type="acronym">INPL</orgName>
<date type="end">2011-12-31</date>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle active="#struct-2496" type="direct"><org type="laboratory" xml:id="struct-2496" status="OLD"><orgName>INRIA Lorraine</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/centre-de-recherche-inria/nancy-grand-est</ref>
</desc>
<listRelation><relation active="#struct-300009" type="direct"></relation>
</listRelation>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
</affiliation>
</author>
<author><name sortKey="Cichon, Adam" sort="Cichon, Adam" uniqKey="Cichon A" first="Adam" last="Cichon">Adam Cichon</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="Touzet, Helene" sort="Touzet, Helene" uniqKey="Touzet H" first="Hélène" last="Touzet">Hélène Touzet</name>
</author>
</analytic>
</biblStruct>
</sourceDesc>
</fileDesc>
<profileDesc><textClass><keywords scheme="mix" xml:lang="fr"><term>DEXP-TIME</term>
<term>EXP-TIME</term>
<term>Interprétation polynomiale</term>
<term>LINSPACE</term>
<term>PTIME</term>
<term>Polynomial interpretation</term>
<term>Rewriting systems</term>
<term>Réécriture</term>
</keywords>
</textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="fr">Les systèmes de réécriture munis d'une interprétation polynomiale ont la propriété de terminaison forte. En fait, et a priori, ainsi que le font remarquer Huet et Oppen, on peut supposer que de telles interprétations sont un bon candidat pour l'étude des fonctions dont la complexité est faible. Ainsi, Cichon et Lescanne ont calculé des bornes de complexité de fonctions unaires selon le type d'interpétation du successeur. Nous nous intéressons plus particulièrement aux fonctions sur les mots qui sont calculables par des systèmes de réécriture munis d'une interprétation polynomiale. Nous les classifions selon un critère basé sur la forme de l'interprétation des constructeurs. Ceci nous conduit à la définition de trois classes qui s'avèrent être exactement : la classe des fonctions calculables en temps polynomial, en temps linéairement exponentiel et en temps doublement exponentiel. d'autre part, nous donnons une caractérisation de l'espace linéaire.</div>
</front>
</TEI>
<hal api="V3"><titleStmt><title xml:lang="en">Complexity classes and rewrite systems with polynomial interpretation</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-2347"></affiliation>
</author>
<author role="aut"><persName><forename type="first">Adam</forename>
<surname>Cichon</surname>
</persName>
<email>cichon@loria.fr</email>
<idno type="halauthor">129548</idno>
</author>
<author role="aut"><persName><forename type="first">Jean-Yves</forename>
<surname>Marion</surname>
</persName>
<email></email>
<idno type="halauthor">63968</idno>
</author>
<author role="aut"><persName><forename type="first">Hélène</forename>
<surname>Touzet</surname>
</persName>
<email></email>
<idno type="halauthor">129705</idno>
</author>
<editor role="depositor"><persName><forename>Publications</forename>
<surname>Loria</surname>
</persName>
<email>publications@loria.fr</email>
</editor>
</titleStmt>
<editionStmt><edition n="v1" type="current"><date type="whenSubmitted">2006-09-26 08:16:58</date>
<date type="whenModified">2016-05-19 01:09:28</date>
<date type="whenReleased">2006-09-28 15:22:44</date>
<date type="whenProduced">1998</date>
<date type="whenEndEmbargoed">2015-02-10</date>
<ref type="file" target="https://hal.inria.fr/inria-00098689/document"><date notBefore="2015-02-10"></date>
</ref>
<ref type="file" n="1" target="https://hal.inria.fr/inria-00098689/file/98-R-060.pdf"><date notBefore="2015-02-10"></date>
</ref>
</edition>
<respStmt><resp>contributor</resp>
<name key="108626"><persName><forename>Publications</forename>
<surname>Loria</surname>
</persName>
<email>publications@loria.fr</email>
</name>
</respStmt>
</editionStmt>
<publicationStmt><distributor>CCSD</distributor>
<idno type="halId">inria-00098689</idno>
<idno type="halUri">https://hal.inria.fr/inria-00098689</idno>
<idno type="halBibtex">bonfante:inria-00098689</idno>
<idno type="halRefHtml">Gottlob, Georg and Etienne, Grand and katrin, Seyr. CSl'98, 1998, Brno, République Tchèque, Springer, 1584, pp.372-384, 1998, Lecture Notes in Computer Science</idno>
<idno type="halRef">Gottlob, Georg and Etienne, Grand and katrin, Seyr. CSl'98, 1998, Brno, République Tchèque, Springer, 1584, pp.372-384, 1998, Lecture Notes in Computer Science</idno>
</publicationStmt>
<seriesStmt><idno type="stamp" n="INRIA">INRIA - Institut National de Recherche en Informatique et en Automatique</idno>
<idno type="stamp" n="CNRS">CNRS - Centre national de la recherche scientifique</idno>
<idno type="stamp" n="INPL">Institut National Polytechnique de Lorraine</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-TALC" p="LORIA">Traitement automatique des langues et des connaissances</idno>
<idno type="stamp" n="LORIA">LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications</idno>
<idno type="stamp" n="UNIV-LORRAINE">Université de Lorraine</idno>
<idno type="stamp" n="INRIA-LORRAINE">INRIA Nancy - Grand Est</idno>
<idno type="stamp" n="LABO-LORIA-SET" p="LORIA">LABO-LORIA-SET</idno>
</seriesStmt>
<notesStmt><note type="commentary">Colloque avec actes sans comité de lecture.</note>
<note type="audience" n="1">Not set</note>
<note type="invited" n="0">No</note>
<note type="popular" n="0">No</note>
<note type="peer" n="1">Yes</note>
<note type="proceedings" n="1">Yes</note>
</notesStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en">Complexity classes and rewrite systems with polynomial interpretation</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-2347"></affiliation>
</author>
<author role="aut"><persName><forename type="first">Adam</forename>
<surname>Cichon</surname>
</persName>
<email>cichon@loria.fr</email>
<idno type="halAuthorId">129548</idno>
</author>
<author role="aut"><persName><forename type="first">Jean-Yves</forename>
<surname>Marion</surname>
</persName>
<idno type="halAuthorId">63968</idno>
</author>
<author role="aut"><persName><forename type="first">Hélène</forename>
<surname>Touzet</surname>
</persName>
<idno type="halAuthorId">129705</idno>
</author>
</analytic>
<monogr><idno type="localRef">98-R-060 || bonfante98a</idno>
<meeting><title>CSl'98</title>
<date type="start">1998</date>
<settlement>Brno, République Tchèque</settlement>
</meeting>
<editor>Gottlob, Georg and Etienne, Grand and katrin, Seyr</editor>
<imprint><publisher>Springer</publisher>
<biblScope unit="serie">Lecture Notes in Computer Science</biblScope>
<biblScope unit="volume">1584</biblScope>
<biblScope unit="pp">372-384</biblScope>
<date type="datePub">1998</date>
</imprint>
</monogr>
</biblStruct>
</sourceDesc>
<profileDesc><langUsage><language ident="en">English</language>
</langUsage>
<textClass><keywords scheme="author"><term xml:lang="fr">Réécriture</term>
<term xml:lang="fr">Rewriting systems</term>
<term xml:lang="fr">Polynomial interpretation</term>
<term xml:lang="fr">PTIME</term>
<term xml:lang="fr">LINSPACE</term>
<term xml:lang="fr">EXP-TIME</term>
<term xml:lang="fr">Interprétation polynomiale</term>
<term xml:lang="fr">DEXP-TIME</term>
</keywords>
<classCode scheme="halDomain" n="info.info-oh">Computer Science [cs]/Other [cs.OH]</classCode>
<classCode scheme="halTypology" n="COMM">Conference papers</classCode>
</textClass>
<abstract xml:lang="fr">Les systèmes de réécriture munis d'une interprétation polynomiale ont la propriété de terminaison forte. En fait, et a priori, ainsi que le font remarquer Huet et Oppen, on peut supposer que de telles interprétations sont un bon candidat pour l'étude des fonctions dont la complexité est faible. Ainsi, Cichon et Lescanne ont calculé des bornes de complexité de fonctions unaires selon le type d'interpétation du successeur. Nous nous intéressons plus particulièrement aux fonctions sur les mots qui sont calculables par des systèmes de réécriture munis d'une interprétation polynomiale. Nous les classifions selon un critère basé sur la forme de l'interprétation des constructeurs. Ceci nous conduit à la définition de trois classes qui s'avèrent être exactement : la classe des fonctions calculables en temps polynomial, en temps linéairement exponentiel et en temps doublement exponentiel. d'autre part, nous donnons une caractérisation de l'espace linéaire.</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 001699 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Hal/Corpus/biblio.hfd -nk 001699 | 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:inria-00098689 |texte= Complexity classes and rewrite systems with polynomial interpretation }}
This area was generated with Dilib version V0.6.33. |