Complexity, Graphs, and the Dependency Pair Method
Identifieur interne : 003A89 ( Istex/Corpus ); précédent : 003A88; suivant : 003A90Complexity, Graphs, and the Dependency Pair Method
Auteurs : Nao Hirokawa ; Georg MoserSource :
- 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
Links to Exploration step
ISTEX:F5E933B0A1E5D83CB7E79366DC34D0E94719C250Le 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><affiliation><mods:affiliation>School of Information Science, Japan Advanced Institute of Science and Technology, Japan</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: hirokawa@jaist.ac.jp</mods:affiliation></affiliation></author><author><name sortKey="Moser, Georg" sort="Moser, Georg" uniqKey="Moser G" first="Georg" last="Moser">Georg Moser</name><affiliation><mods:affiliation>Institute of Computer Science, University of Innsbruck, Austria</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: georg.moser@uibk.ac.at</mods:affiliation></affiliation></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></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><mods:affiliation>School of Information Science, Japan Advanced Institute of Science and Technology, Japan</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: hirokawa@jaist.ac.jp</mods:affiliation></affiliation></author><author><name sortKey="Moser, Georg" sort="Moser, Georg" uniqKey="Moser G" first="Georg" last="Moser">Georg Moser</name><affiliation><mods:affiliation>Institute of Computer Science, University of Innsbruck, Austria</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: georg.moser@uibk.ac.at</mods:affiliation></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><istex><corpusName>springer-ebooks</corpusName><author><json:item><name>Nao Hirokawa</name><affiliations><json:string>School of Information Science, Japan Advanced Institute of Science and Technology, Japan</json:string><json:string>E-mail: hirokawa@jaist.ac.jp</json:string></affiliations></json:item><json:item><name>Georg Moser</name><affiliations><json:string>Institute of Computer Science, University of Innsbruck, Austria</json:string><json:string>E-mail: georg.moser@uibk.ac.at</json:string></affiliations></json:item></author><arkIstex>ark:/67375/HCB-GWCLWF7S-G</arkIstex><language><json:string>eng</json:string></language><originalGenre><json:string>OriginalPaper</json:string></originalGenre><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.</abstract><qualityIndicators><refBibsNative>false</refBibsNative><abstractWordCount>99</abstractWordCount><abstractCharCount>674</abstractCharCount><keywordCount>0</keywordCount><score>8.188</score><pdfWordCount>7769</pdfWordCount><pdfCharCount>34715</pdfCharCount><pdfVersion>1.6</pdfVersion><pdfPageCount>15</pdfPageCount><pdfPageSize>430 x 660 pts</pdfPageSize></qualityIndicators><title>Complexity, Graphs, and the Dependency Pair Method</title><chapterId><json:string>45</json:string><json:string>Chap45</json:string></chapterId><genre><json:string>conference</json:string></genre><serie><title>Lecture Notes in Computer Science</title><language><json:string>unknown</json:string></language><copyrightDate>2008</copyrightDate><issn><json:string>0302-9743</json:string></issn><eissn><json:string>1611-3349</json:string></eissn></serie><host><title>Logic for Programming, Artificial Intelligence, and Reasoning</title><language><json:string>unknown</json:string></language><copyrightDate>2008</copyrightDate><doi><json:string>10.1007/978-3-540-89439-1</json:string></doi><issn><json:string>0302-9743</json:string></issn><eissn><json:string>1611-3349</json:string></eissn><eisbn><json:string>978-3-540-89439-1</json:string></eisbn><bookId><json:string>978-3-540-89439-1</json:string></bookId><isbn><json:string>978-3-540-89438-4</json:string></isbn><volume>5330</volume><pages><first>652</first><last>666</last></pages><genre><json:string>book-series</json:string></genre><editor><json:item><name>Iliano Cervesato</name><affiliations><json:string>Carnegie Mellon University, Doha, Qatar</json:string></affiliations></json:item><json:item><name>Helmut Veith</name><affiliations><json:string>Technische Universität Darmstadt, Germany</json:string></affiliations></json:item><json:item><name>Andrei Voronkov</name><affiliations><json:string>University of Manchester, UK</json:string></affiliations></json:item></editor><subject><json:item><value>Computer Science</value></json:item><json:item><value>Computer Science</value></json:item><json:item><value>Artificial Intelligence (incl. Robotics)</value></json:item><json:item><value>Programming Techniques</value></json:item><json:item><value>Software Engineering</value></json:item><json:item><value>Logics and Meanings of Programs</value></json:item><json:item><value>Mathematical Logic and Formal Languages</value></json:item></subject></host><ark><json:string>ark:/67375/HCB-GWCLWF7S-G</json:string></ark><publicationDate>2008</publicationDate><copyrightDate>2008</copyrightDate><doi><json:string>10.1007/978-3-540-89439-1_45</json:string></doi><id>F5E933B0A1E5D83CB7E79366DC34D0E94719C250</id><score>1</score><fulltext><json:item><extension>pdf</extension><original>true</original><mimetype>application/pdf</mimetype><uri>https://api.istex.fr/ark:/67375/HCB-GWCLWF7S-G/fulltext.pdf</uri></json:item><json:item><extension>zip</extension><original>false</original><mimetype>application/zip</mimetype><uri>https://api.istex.fr/ark:/67375/HCB-GWCLWF7S-G/bundle.zip</uri></json:item><istex:fulltextTEI uri="https://api.istex.fr/ark:/67375/HCB-GWCLWF7S-G/fulltext.tei"><teiHeader><fileDesc><titleStmt><title level="a" type="main" xml:lang="en">Complexity, Graphs, and the Dependency Pair Method</title></titleStmt><publicationStmt><authority>ISTEX</authority><availability><licence>Springer-Verlag Berlin Heidelberg</licence></availability><date when="2008">2008</date></publicationStmt><notesStmt><note type="conference" source="proceedings" scheme="https://content-type.data.istex.fr/ark:/67375/XTP-BFHXPBJJ-3">conference</note><note type="publication-type" subtype="book-series" scheme="https://publication-type.data.istex.fr/ark:/67375/JMC-0G6R5W5T-Z">book-series</note></notesStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Complexity, Graphs, and the Dependency Pair Method</title><author><persName><forename type="first">Nao</forename><surname>Hirokawa</surname></persName><email>hirokawa@jaist.ac.jp</email><affiliation><orgName type="department">School of Information Science</orgName><orgName type="institution">Japan Advanced Institute of Science and Technology</orgName><address><country key="JP">JAPAN</country></address></affiliation></author><author><persName><forename type="first">Georg</forename><surname>Moser</surname></persName><email>georg.moser@uibk.ac.at</email><affiliation><orgName type="department">Institute of Computer Science</orgName><orgName type="institution">University of Innsbruck</orgName><address><country key="AT">AUSTRIA</country></address></affiliation></author><idno type="istex">F5E933B0A1E5D83CB7E79366DC34D0E94719C250</idno><idno type="ark">ark:/67375/HCB-GWCLWF7S-G</idno><idno type="DOI">10.1007/978-3-540-89439-1_45</idno></analytic><monogr><title level="m" type="main">Logic for Programming, Artificial Intelligence, and Reasoning</title><title level="m" type="sub">15th International Conference, LPAR 2008, Doha, Qatar, November 22-27, 2008. Proceedings</title><title level="m" type="part">Session 11. Rewriting</title><idno type="DOI">10.1007/978-3-540-89439-1</idno><idno type="book-id">978-3-540-89439-1</idno><idno type="ISBN">978-3-540-89438-4</idno><idno type="eISBN">978-3-540-89439-1</idno><idno type="chapter-id">Chap45</idno><idno type="part-id">Part13</idno><editor><persName><forename type="first">Iliano</forename><surname>Cervesato</surname></persName><affiliation><orgName type="institution">Carnegie Mellon University, Doha</orgName><address><settlement>Qatar</settlement></address></affiliation></editor><editor><persName><forename type="first">Helmut</forename><surname>Veith</surname></persName><affiliation><orgName type="institution">Technische Universität Darmstadt</orgName><address><country key="DE">GERMANY</country></address></affiliation></editor><editor><persName><forename type="first">Andrei</forename><surname>Voronkov</surname></persName><affiliation><orgName type="institution">University of Manchester</orgName><address><country key="GB">UNITED KINGDOM</country></address></affiliation></editor><imprint><biblScope unit="vol">5330</biblScope><biblScope unit="page" from="652">652</biblScope><biblScope unit="page" to="666">666</biblScope><biblScope unit="chapter-count">49</biblScope><biblScope unit="part-chapter-count">6</biblScope></imprint></monogr><series><title level="s" type="main" xml:lang="en">Lecture Notes in Computer Science</title><idno type="pISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="seriesID">558</idno></series></biblStruct></sourceDesc></fileDesc><profileDesc><abstract xml:lang="en"><head>Abstract</head><p>This paper builds on recent efforts (Hirokawa and Moser, 2008) to exploit the dependency pair method for verifying feasible, i.e., polynomial <hi rend="italic">runtime complexities</hi> 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 <hi rend="italic">feasible</hi> runtime complexities. We provide ample numerical data for assessing the viability of the method.</p></abstract><textClass ana="subject"><keywords scheme="book-subject-collection"><list><label>SUCO11645</label><item><term>Computer Science</term></item></list></keywords></textClass><textClass ana="subject"><keywords scheme="book-subject"><list><label>I</label><item><term type="Primary">Computer Science</term></item><label>I21017</label><item><term type="Secondary" subtype="priority-1">Artificial Intelligence (incl. Robotics)</term></item><label>I14010</label><item><term type="Secondary" subtype="priority-2">Programming Techniques</term></item><label>I14029</label><item><term type="Secondary" subtype="priority-3">Software Engineering</term></item><label>I1603X</label><item><term type="Secondary" subtype="priority-4">Logics and Meanings of Programs</term></item><label>I16048</label><item><term type="Secondary" subtype="priority-5">Mathematical Logic and Formal Languages</term></item></list></keywords></textClass><langUsage><language ident="EN"></language></langUsage></profileDesc></teiHeader></istex:fulltextTEI><json:item><extension>txt</extension><original>false</original><mimetype>text/plain</mimetype><uri>https://api.istex.fr/ark:/67375/HCB-GWCLWF7S-G/fulltext.txt</uri></json:item></fulltext><metadata><istex:metadataXml wicri:clean="corpus springer-ebooks not found" wicri:toSee="no header"><istex:xmlDeclaration>version="1.0" encoding="UTF-8"</istex:xmlDeclaration><istex:docType PUBLIC="-//Springer-Verlag//DTD A++ V2.4//EN" URI="http://devel.springer.de/A++/V2.4/DTD/A++V2.4.dtd" name="istex:docType"></istex:docType><istex:document><Publisher><PublisherInfo><PublisherName>Springer Berlin Heidelberg</PublisherName><PublisherLocation>Berlin, Heidelberg</PublisherLocation></PublisherInfo><Series><SeriesInfo SeriesType="Series" TocLevels="0"><SeriesID>558</SeriesID><SeriesPrintISSN>0302-9743</SeriesPrintISSN><SeriesElectronicISSN>1611-3349</SeriesElectronicISSN><SeriesTitle Language="En">Lecture Notes in Computer Science</SeriesTitle></SeriesInfo><SubSeries><SubSeriesInfo><SubSeriesID>1244</SubSeriesID><SubSeriesPrintISSN>0302-9743</SubSeriesPrintISSN><SubSeriesElectronicISSN>1611-3349</SubSeriesElectronicISSN><SubSeriesTitle Language="En">Lecture Notes in Artificial Intelligence</SubSeriesTitle></SubSeriesInfo><SubSeriesHeader><EditorGroup><Editor><EditorName DisplayOrder="Western"><GivenName>Jaime</GivenName><GivenName>G.</GivenName><FamilyName>Carbonell</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Jörg</GivenName><FamilyName>Siekmann</FamilyName></EditorName></Editor></EditorGroup></SubSeriesHeader></SubSeries><Book Language="En"><BookInfo BookProductType="Proceedings" ContainsESM="No" Language="En" MediaType="eBook" NumberingStyle="Unnumbered" OutputMedium="All" TocLevels="0"><BookID>978-3-540-89439-1</BookID><BookTitle>Logic for Programming, Artificial Intelligence, and Reasoning</BookTitle><BookSubTitle>15th International Conference, LPAR 2008, Doha, Qatar, November 22-27, 2008. Proceedings</BookSubTitle><BookVolumeNumber>5330</BookVolumeNumber><BookSequenceNumber>5330</BookSequenceNumber><BookDOI>10.1007/978-3-540-89439-1</BookDOI><BookTitleID>184471</BookTitleID><BookPrintISBN>978-3-540-89438-4</BookPrintISBN><BookElectronicISBN>978-3-540-89439-1</BookElectronicISBN><BookChapterCount>49</BookChapterCount><BookCopyright><CopyrightHolderName>Springer Berlin Heidelberg</CopyrightHolderName><CopyrightYear>2008</CopyrightYear></BookCopyright><BookSubjectGroup><BookSubject Code="I" Type="Primary">Computer Science</BookSubject><BookSubject Code="I21017" Priority="1" Type="Secondary">Artificial Intelligence (incl. Robotics)</BookSubject><BookSubject Code="I14010" Priority="2" Type="Secondary">Programming Techniques</BookSubject><BookSubject Code="I14029" Priority="3" Type="Secondary">Software Engineering</BookSubject><BookSubject Code="I1603X" Priority="4" Type="Secondary">Logics and Meanings of Programs</BookSubject><BookSubject Code="I16048" Priority="5" Type="Secondary">Mathematical Logic and Formal Languages</BookSubject><SubjectCollection Code="SUCO11645">Computer Science</SubjectCollection></BookSubjectGroup></BookInfo><BookHeader><EditorGroup><Editor AffiliationIDS="Aff1"><EditorName DisplayOrder="Western"><GivenName>Iliano</GivenName><FamilyName>Cervesato</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff2"><EditorName DisplayOrder="Western"><GivenName>Helmut</GivenName><FamilyName>Veith</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff3"><EditorName DisplayOrder="Western"><GivenName>Andrei</GivenName><FamilyName>Voronkov</FamilyName></EditorName></Editor><Affiliation ID="Aff1"><OrgName>Carnegie Mellon University, Doha</OrgName><OrgAddress><City>Qatar</City></OrgAddress></Affiliation><Affiliation ID="Aff2"><OrgName>Technische Universität Darmstadt</OrgName><OrgAddress><Country>Germany</Country></OrgAddress></Affiliation><Affiliation ID="Aff3"><OrgName>University of Manchester</OrgName><OrgAddress><Country>UK</Country></OrgAddress></Affiliation></EditorGroup></BookHeader><Part ID="Part13"><PartInfo TocLevels="0"><PartID>13</PartID><PartSequenceNumber>13</PartSequenceNumber><PartTitle>Session 11. Rewriting</PartTitle><PartChapterCount>6</PartChapterCount><PartContext><SeriesID>558</SeriesID><BookTitle>Logic for Programming, Artificial Intelligence, and Reasoning</BookTitle></PartContext></PartInfo><Chapter ID="Chap45" Language="En"><ChapterInfo ChapterType="OriginalPaper" ContainsESM="No" NumberingStyle="Unnumbered" TocLevels="0"><ChapterID>45</ChapterID><ChapterDOI>10.1007/978-3-540-89439-1_45</ChapterDOI><ChapterSequenceNumber>45</ChapterSequenceNumber><ChapterTitle Language="En">Complexity, Graphs, and the Dependency Pair Method</ChapterTitle><ChapterFirstPage>652</ChapterFirstPage><ChapterLastPage>666</ChapterLastPage><ChapterCopyright><CopyrightHolderName>Springer-Verlag Berlin Heidelberg</CopyrightHolderName><CopyrightYear>2008</CopyrightYear></ChapterCopyright><ChapterGrants Type="Regular"><MetadataGrant Grant="OpenAccess"></MetadataGrant><AbstractGrant Grant="OpenAccess"></AbstractGrant><BodyPDFGrant Grant="Restricted"></BodyPDFGrant><BodyHTMLGrant Grant="Restricted"></BodyHTMLGrant><BibliographyGrant Grant="Restricted"></BibliographyGrant><ESMGrant Grant="Restricted"></ESMGrant></ChapterGrants><ChapterContext><SeriesID>558</SeriesID><PartID>13</PartID><BookID>978-3-540-89439-1</BookID><BookTitle>Logic for Programming, Artificial Intelligence, and Reasoning</BookTitle></ChapterContext></ChapterInfo><ChapterHeader><AuthorGroup><Author AffiliationIDS="Aff4"><AuthorName DisplayOrder="Western"><GivenName>Nao</GivenName><FamilyName>Hirokawa</FamilyName></AuthorName><Contact><Email>hirokawa@jaist.ac.jp</Email></Contact></Author><Author AffiliationIDS="Aff5"><AuthorName DisplayOrder="Western"><GivenName>Georg</GivenName><FamilyName>Moser</FamilyName></AuthorName><Contact><Email>georg.moser@uibk.ac.at</Email></Contact></Author><Affiliation ID="Aff4"><OrgDivision>School of Information Science</OrgDivision><OrgName>Japan Advanced Institute of Science and Technology</OrgName><OrgAddress><Country>Japan</Country></OrgAddress></Affiliation><Affiliation ID="Aff5"><OrgDivision>Institute of Computer Science</OrgDivision><OrgName>University of Innsbruck</OrgName><OrgAddress><Country>Austria</Country></OrgAddress></Affiliation></AuthorGroup><Abstract ID="Abs1" Language="En"><Heading>Abstract</Heading><Para>This paper builds on recent efforts (Hirokawa and Moser, 2008) to exploit the dependency pair method for verifying feasible, i.e., polynomial <Emphasis Type="Italic">runtime complexities</Emphasis> 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 <Emphasis Type="Italic">feasible</Emphasis> runtime complexities. We provide ample numerical data for assessing the viability of the method.</Para></Abstract><ArticleNote Type="Misc"><SimplePara>This research is partly supported by FWF (Austrian Science Fund) project P20133, Grant-in-Aid for Young Scientists 20800022 of the Ministry of Education, Culture, Sports, Science and Technology of Japan, and STARC.</SimplePara></ArticleNote></ChapterHeader><NoBody></NoBody></Chapter></Part></Book></Series></Publisher></istex:document></istex:metadataXml><mods version="3.6"><titleInfo lang="en"><title>Complexity, Graphs, and the Dependency Pair Method</title></titleInfo><titleInfo type="alternative" contentType="CDATA"><title>Complexity, Graphs, and the Dependency Pair Method</title></titleInfo><name type="personal"><namePart type="given">Nao</namePart><namePart type="family">Hirokawa</namePart><affiliation>School of Information Science, Japan Advanced Institute of Science and Technology, Japan</affiliation><affiliation>E-mail: hirokawa@jaist.ac.jp</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">Georg</namePart><namePart type="family">Moser</namePart><affiliation>Institute of Computer Science, University of Innsbruck, Austria</affiliation><affiliation>E-mail: georg.moser@uibk.ac.at</affiliation><role><roleTerm type="text">author</roleTerm></role></name><typeOfResource>text</typeOfResource><genre displayLabel="OriginalPaper" authority="ISTEX" authorityURI="https://content-type.data.istex.fr" type="conference" valueURI="https://content-type.data.istex.fr/ark:/67375/XTP-BFHXPBJJ-3">conference</genre><originInfo><publisher>Springer Berlin Heidelberg</publisher><place><placeTerm type="text">Berlin, Heidelberg</placeTerm></place><dateIssued encoding="w3cdtf">2008</dateIssued><copyrightDate encoding="w3cdtf">2008</copyrightDate></originInfo><language><languageTerm type="code" authority="rfc3066">en</languageTerm><languageTerm type="code" authority="iso639-2b">eng</languageTerm></language><abstract 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.</abstract><relatedItem type="host"><titleInfo><title>Logic for Programming, Artificial Intelligence, and Reasoning</title><subTitle>15th International Conference, LPAR 2008, Doha, Qatar, November 22-27, 2008. Proceedings</subTitle></titleInfo><name type="personal"><namePart type="given">Iliano</namePart><namePart type="family">Cervesato</namePart><affiliation>Carnegie Mellon University, Doha, Qatar</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Helmut</namePart><namePart type="family">Veith</namePart><affiliation>Technische Universität Darmstadt, Germany</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Andrei</namePart><namePart type="family">Voronkov</namePart><affiliation>University of Manchester, UK</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><genre type="book-series" authority="ISTEX" authorityURI="https://publication-type.data.istex.fr" valueURI="https://publication-type.data.istex.fr/ark:/67375/JMC-0G6R5W5T-Z">book-series</genre><originInfo><publisher>Springer</publisher><copyrightDate encoding="w3cdtf">2008</copyrightDate><issuance>monographic</issuance></originInfo><subject><genre>Book-Subject-Collection</genre><topic authority="SpringerSubjectCodes" authorityURI="SUCO11645">Computer Science</topic></subject><subject><genre>Book-Subject-Group</genre><topic authority="SpringerSubjectCodes" authorityURI="I">Computer Science</topic><topic authority="SpringerSubjectCodes" authorityURI="I21017">Artificial Intelligence (incl. Robotics)</topic><topic authority="SpringerSubjectCodes" authorityURI="I14010">Programming Techniques</topic><topic authority="SpringerSubjectCodes" authorityURI="I14029">Software Engineering</topic><topic authority="SpringerSubjectCodes" authorityURI="I1603X">Logics and Meanings of Programs</topic><topic authority="SpringerSubjectCodes" authorityURI="I16048">Mathematical Logic and Formal Languages</topic></subject><identifier type="DOI">10.1007/978-3-540-89439-1</identifier><identifier type="ISBN">978-3-540-89438-4</identifier><identifier type="eISBN">978-3-540-89439-1</identifier><identifier type="ISSN">0302-9743</identifier><identifier type="eISSN">1611-3349</identifier><identifier type="BookTitleID">184471</identifier><identifier type="BookID">978-3-540-89439-1</identifier><identifier type="BookChapterCount">49</identifier><identifier type="BookVolumeNumber">5330</identifier><identifier type="BookSequenceNumber">5330</identifier><identifier type="PartChapterCount">6</identifier><part><date>2008</date><detail type="part"><title>Session 11. Rewriting</title></detail><detail type="volume"><number>5330</number><caption>vol.</caption></detail><extent unit="pages"><start>652</start><end>666</end></extent></part><recordInfo><recordOrigin>Springer Berlin Heidelberg, 2008</recordOrigin></recordInfo></relatedItem><relatedItem type="series"><titleInfo><title>Lecture Notes in Computer Science</title></titleInfo><originInfo><publisher>Springer</publisher><copyrightDate encoding="w3cdtf">2008</copyrightDate><issuance>serial</issuance></originInfo><relatedItem type="constituent"><titleInfo><title>Lecture Notes in Artificial Intelligence</title></titleInfo><name type="personal"><namePart type="given">Jaime</namePart><namePart type="given">G.</namePart><namePart type="family">Carbonell</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Jörg</namePart><namePart type="family">Siekmann</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Iliano</namePart><namePart type="family">Cervesato</namePart><affiliation>Carnegie Mellon University, Doha, Qatar</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Helmut</namePart><namePart type="family">Veith</namePart><affiliation>Technische Universität Darmstadt, Germany</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Andrei</namePart><namePart type="family">Voronkov</namePart><affiliation>University of Manchester, UK</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><genre type="sub-series"></genre><identifier type="ISSN">0302-9743</identifier><identifier type="eISSN">1611-3349</identifier><identifier type="SubSeriesID">1244</identifier></relatedItem><identifier type="ISSN">0302-9743</identifier><identifier type="eISSN">1611-3349</identifier><identifier type="SeriesID">558</identifier><recordInfo><recordOrigin>Springer Berlin Heidelberg, 2008</recordOrigin></recordInfo></relatedItem><identifier type="istex">F5E933B0A1E5D83CB7E79366DC34D0E94719C250</identifier><identifier type="ark">ark:/67375/HCB-GWCLWF7S-G</identifier><identifier type="DOI">10.1007/978-3-540-89439-1_45</identifier><identifier type="ChapterID">45</identifier><identifier type="ChapterID">Chap45</identifier><accessCondition type="use and reproduction" contentType="copyright">Springer Berlin Heidelberg, 2008</accessCondition><recordInfo><recordContentSource authority="ISTEX" authorityURI="https://loaded-corpus.data.istex.fr" valueURI="https://loaded-corpus.data.istex.fr/ark:/67375/XBH-RLRX46XW-4">springer</recordContentSource><recordOrigin>Springer-Verlag Berlin Heidelberg, 2008</recordOrigin></recordInfo></mods><json:item><extension>json</extension><original>false</original><mimetype>application/json</mimetype><uri>https://api.istex.fr/ark:/67375/HCB-GWCLWF7S-G/record.json</uri></json:item></metadata></istex></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Istex/Corpus
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 003A89 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Corpus/biblio.hfd -nk 003A89 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Istex
|étape= Corpus
|type= RBID
|clé= ISTEX:F5E933B0A1E5D83CB7E79366DC34D0E94719C250
|texte= Complexity, Graphs, and the Dependency Pair Method
}}
| This area was generated with Dilib version V0.6.33. |  |