Complexity, Graphs, and the Dependency Pair Method
Identifieur interne : 004409 ( Main/Exploration ); précédent : 004408; suivant : 004410Complexity, Graphs, and the Dependency Pair Method
Auteurs : Nao Hirokawa [Japon] ; Georg Moser [Autriche]Source :
- Lecture Notes in Computer Science [ 0302-9743 ]
Abstract
Abstract: This paper builds on recent efforts (Hirokawa and Moser, 2008) to exploit the dependency pair method for verifying feasible, i.e., polynomial runtime complexities of term rewrite systems automatically. We extend our earlier results by revisiting dependency graphs in the context of complexity analysis. The obtained new results are easy to implement and considerably extend the analytic power of our existing methods. The gain in power is even more significant when compared to existing methods that directly, i.e., without the use of transformations, induce feasible runtime complexities. We provide ample numerical data for assessing the viability of the method.
Url:
DOI: 10.1007/978-3-540-89439-1_45
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 003A89
- to stream Istex, to step Curation: 003A45
- to stream Istex, to step Checkpoint: 000E37
- to stream Main, to step Merge: 004520
- to stream Main, to step Curation: 004409
Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Complexity, Graphs, and the Dependency Pair Method</title><author><name sortKey="Hirokawa, Nao" sort="Hirokawa, Nao" uniqKey="Hirokawa N" first="Nao" last="Hirokawa">Nao Hirokawa</name></author><author><name sortKey="Moser, Georg" sort="Moser, Georg" uniqKey="Moser G" first="Georg" last="Moser">Georg Moser</name></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:F5E933B0A1E5D83CB7E79366DC34D0E94719C250</idno><date when="2008" year="2008">2008</date><idno type="doi">10.1007/978-3-540-89439-1_45</idno><idno type="url">https://api.istex.fr/ark:/67375/HCB-GWCLWF7S-G/fulltext.pdf</idno><idno type="wicri:Area/Istex/Corpus">003A89</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">003A89</idno><idno type="wicri:Area/Istex/Curation">003A45</idno><idno type="wicri:Area/Istex/Checkpoint">000E37</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">000E37</idno><idno type="wicri:doubleKey">0302-9743:2008:Hirokawa N:complexity:graphs:and</idno><idno type="wicri:Area/Main/Merge">004520</idno><idno type="wicri:Area/Main/Curation">004409</idno><idno type="wicri:Area/Main/Exploration">004409</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Complexity, Graphs, and the Dependency Pair Method</title><author><name sortKey="Hirokawa, Nao" sort="Hirokawa, Nao" uniqKey="Hirokawa N" first="Nao" last="Hirokawa">Nao Hirokawa</name><affiliation wicri:level="1"><country xml:lang="fr">Japon</country><wicri:regionArea>School of Information Science, Japan Advanced Institute of Science and Technology</wicri:regionArea><wicri:noRegion>Japan Advanced Institute of Science and Technology</wicri:noRegion></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Japon</country></affiliation></author><author><name sortKey="Moser, Georg" sort="Moser, Georg" uniqKey="Moser G" first="Georg" last="Moser">Georg Moser</name><affiliation wicri:level="1"><country xml:lang="fr">Autriche</country><wicri:regionArea>Institute of Computer Science, University of Innsbruck</wicri:regionArea><wicri:noRegion>University of Innsbruck</wicri:noRegion></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Autriche</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: This paper builds on recent efforts (Hirokawa and Moser, 2008) to exploit the dependency pair method for verifying feasible, i.e., polynomial runtime complexities of term rewrite systems automatically. We extend our earlier results by revisiting dependency graphs in the context of complexity analysis. The obtained new results are easy to implement and considerably extend the analytic power of our existing methods. The gain in power is even more significant when compared to existing methods that directly, i.e., without the use of transformations, induce feasible runtime complexities. We provide ample numerical data for assessing the viability of the method.</div></front></TEI><affiliations><list><country><li>Autriche</li><li>Japon</li></country></list><tree><country name="Japon"><noRegion><name sortKey="Hirokawa, Nao" sort="Hirokawa, Nao" uniqKey="Hirokawa N" first="Nao" last="Hirokawa">Nao Hirokawa</name></noRegion><name sortKey="Hirokawa, Nao" sort="Hirokawa, Nao" uniqKey="Hirokawa N" first="Nao" last="Hirokawa">Nao Hirokawa</name></country><country name="Autriche"><noRegion><name sortKey="Moser, Georg" sort="Moser, Georg" uniqKey="Moser G" first="Georg" last="Moser">Georg Moser</name></noRegion><name sortKey="Moser, Georg" sort="Moser, Georg" uniqKey="Moser G" first="Georg" last="Moser">Georg Moser</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 004409 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 004409 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Main
|étape= Exploration
|type= RBID
|clé= ISTEX:F5E933B0A1E5D83CB7E79366DC34D0E94719C250
|texte= Complexity, Graphs, and the Dependency Pair Method
}}
| This area was generated with Dilib version V0.6.33. |  |