Complexity Classes and Rewrite Systems with Polynomial Interpretation
Identifieur interne : 00B081 ( Main/Merge ); précédent : 00B080; suivant : 00B082Complexity Classes and Rewrite Systems with Polynomial Interpretation
Auteurs : G. Bonfante [France] ; A. Cichon [France] ; J. Y. Marion [France] ; H. Touzet [France]Source :
- Lecture Notes in Computer Science [ 0302-9743 ]
Abstract
Abstract: We are concerned with functions over words which are computable by means of a rewrite system admitting polynomial interpretation termination proofs. We classify them according to the interpretations of successor symbols. This leads to the definition of three classes, which turn out to be exactly the poly-time, linear exponential-time and doubly linear exponential time computable functions. As a consequence, we also characterize the linear space computable functions.
Url:
DOI: 10.1007/10703163_25
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 002968
- to stream Istex, to step Curation: 002932
- to stream Istex, to step Checkpoint: 002415
Links to Exploration step
ISTEX:AFE957BF88B07F168C00C072A9C8D10516D97ED8Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Complexity Classes and Rewrite Systems with Polynomial Interpretation</title><author><name sortKey="Bonfante, G" sort="Bonfante, G" uniqKey="Bonfante G" first="G." last="Bonfante">G. Bonfante</name></author><author><name sortKey="Cichon, A" sort="Cichon, A" uniqKey="Cichon A" first="A." last="Cichon">A. Cichon</name></author><author><name sortKey="Marion, J Y" sort="Marion, J Y" uniqKey="Marion J" first="J. Y" last="Marion">J. Y. Marion</name></author><author><name sortKey="Touzet, H" sort="Touzet, H" uniqKey="Touzet H" first="H." last="Touzet">H. Touzet</name></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:AFE957BF88B07F168C00C072A9C8D10516D97ED8</idno><date when="1999" year="1999">1999</date><idno type="doi">10.1007/10703163_25</idno><idno type="url">https://api.istex.fr/ark:/67375/HCB-369QCZWC-M/fulltext.pdf</idno><idno type="wicri:Area/Istex/Corpus">002968</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">002968</idno><idno type="wicri:Area/Istex/Curation">002932</idno><idno type="wicri:Area/Istex/Checkpoint">002415</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">002415</idno><idno type="wicri:doubleKey">0302-9743:1999:Bonfante G:complexity:classes:and</idno><idno type="wicri:Area/Main/Merge">00B081</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Complexity Classes and Rewrite Systems with Polynomial Interpretation</title><author><name sortKey="Bonfante, G" sort="Bonfante, G" uniqKey="Bonfante G" first="G." last="Bonfante">G. Bonfante</name><affiliation wicri:level="3"><country xml:lang="fr">France</country><wicri:regionArea>Loria, Calligramme project, B.P. 239, 54506, Vandœuvre-lès-Nancy Cedex</wicri:regionArea><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"><country wicri:rule="url">France</country></affiliation></author><author><name sortKey="Cichon, A" sort="Cichon, A" uniqKey="Cichon A" first="A." last="Cichon">A. Cichon</name><affiliation wicri:level="3"><country xml:lang="fr">France</country><wicri:regionArea>Loria, Calligramme project, B.P. 239, 54506, Vandœuvre-lès-Nancy Cedex</wicri:regionArea><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"><country wicri:rule="url">France</country></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"><country xml:lang="fr">France</country><wicri:regionArea>Loria, Calligramme project, B.P. 239, 54506, Vandœuvre-lès-Nancy Cedex</wicri:regionArea><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"><country wicri:rule="url">France</country></affiliation></author><author><name sortKey="Touzet, H" sort="Touzet, H" uniqKey="Touzet H" first="H." last="Touzet">H. Touzet</name><affiliation wicri:level="3"><country xml:lang="fr">France</country><wicri:regionArea>Loria, Calligramme project, B.P. 239, 54506, Vandœuvre-lès-Nancy Cedex</wicri:regionArea><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"><country wicri:rule="url">France</country></affiliation></author></analytic><monogr></monogr><series><title level="s" type="main" xml:lang="en">Lecture Notes in Computer Science</title><idno type="ISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="ISSN">0302-9743</idno></series></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0302-9743</idno></seriesStmt></fileDesc><profileDesc><textClass></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: We are concerned with functions over words which are computable by means of a rewrite system admitting polynomial interpretation termination proofs. We classify them according to the interpretations of successor symbols. This leads to the definition of three classes, which turn out to be exactly the poly-time, linear exponential-time and doubly linear exponential time computable functions. As a consequence, we also characterize the linear space computable functions.</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 00B081 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Merge/biblio.hfd -nk 00B081 | 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é= ISTEX:AFE957BF88B07F168C00C072A9C8D10516D97ED8
|texte= Complexity Classes and Rewrite Systems with Polynomial Interpretation
}}
| This area was generated with Dilib version V0.6.33. |  |