Automatic Complexity Analysis
Identifieur interne : 001C63 ( Main/Curation ); précédent : 001C62; suivant : 001C64Automatic Complexity Analysis
Auteurs : Flemming Nielson [Danemark] ; Hanne Riis Nielson [Danemark] ; Helmut Seidl [Allemagne]Source :
- Lecture Notes in Computer Science [ 0302-9743 ] ; 2002.
Descripteurs français
- Pascal (Inist)
English descriptors
Abstract
Abstract: We consider the problem of automating the derivation of tight asymptotic complexity bounds for solving Horn clauses. Clearly, the solving time crucially depends on the “sparseness” of the computed relations. Therefore, our asymptotic runtime analysis is accompanied by an asymptotic sparsity calculus together with an asymptotic sparsity analysis. The technical problem here is that least fixpoint iteration fails on asymptotic complexity expressions: the intuitive reason is that O(1)+ srO(1) = O(1) but O(1) + ⋯ + O(1) may return any value.
Url:
DOI: 10.1007/3-540-45927-8_18
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: Pour aller vers cette notice dans l'étape Curation :001112
- to stream Istex, to step Curation: Pour aller vers cette notice dans l'étape Curation :001001
- to stream Istex, to step Checkpoint: Pour aller vers cette notice dans l'étape Curation :000B72
- to stream Main, to step Merge: Pour aller vers cette notice dans l'étape Curation :001F12
- to stream PascalFrancis, to step Corpus: Pour aller vers cette notice dans l'étape Curation :000D48
- to stream PascalFrancis, to step Curation: Pour aller vers cette notice dans l'étape Curation :000188
- to stream PascalFrancis, to step Checkpoint: Pour aller vers cette notice dans l'étape Curation :000B22
- to stream Main, to step Merge: Pour aller vers cette notice dans l'étape Curation :001F87
Links to Exploration step
ISTEX:EB7186CC090D19320A84864F0CB4065CC4B95D28Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Automatic Complexity Analysis</title>
<author><name sortKey="Nielson, Flemming" sort="Nielson, Flemming" uniqKey="Nielson F" first="Flemming" last="Nielson">Flemming Nielson</name>
</author>
<author><name sortKey="Nielson, Hanne Riis" sort="Nielson, Hanne Riis" uniqKey="Nielson H" first="Hanne Riis" last="Nielson">Hanne Riis Nielson</name>
</author>
<author><name sortKey="Seidl, Helmut" sort="Seidl, Helmut" uniqKey="Seidl H" first="Helmut" last="Seidl">Helmut Seidl</name>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">ISTEX</idno>
<idno type="RBID">ISTEX:EB7186CC090D19320A84864F0CB4065CC4B95D28</idno>
<date when="2002" year="2002">2002</date>
<idno type="doi">10.1007/3-540-45927-8_18</idno>
<idno type="url">https://api.istex.fr/document/EB7186CC090D19320A84864F0CB4065CC4B95D28/fulltext/pdf</idno>
<idno type="wicri:Area/Istex/Corpus">001112</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">001112</idno>
<idno type="wicri:Area/Istex/Curation">001001</idno>
<idno type="wicri:Area/Istex/Checkpoint">000B72</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">000B72</idno>
<idno type="wicri:doubleKey">0302-9743:2002:Nielson F:automatic:complexity:analysis</idno>
<idno type="wicri:Area/Main/Merge">001F12</idno>
<idno type="wicri:source">INIST</idno>
<idno type="RBID">Pascal:02-0318071</idno>
<idno type="wicri:Area/PascalFrancis/Corpus">000D48</idno>
<idno type="wicri:Area/PascalFrancis/Curation">000188</idno>
<idno type="wicri:Area/PascalFrancis/Checkpoint">000B22</idno>
<idno type="wicri:explorRef" wicri:stream="PascalFrancis" wicri:step="Checkpoint">000B22</idno>
<idno type="wicri:doubleKey">0302-9743:2002:Nielson F:automatic:complexity:analysis</idno>
<idno type="wicri:Area/Main/Merge">001F87</idno>
<idno type="wicri:Area/Main/Curation">001C63</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Automatic Complexity Analysis</title>
<author><name sortKey="Nielson, Flemming" sort="Nielson, Flemming" uniqKey="Nielson F" first="Flemming" last="Nielson">Flemming Nielson</name>
<affiliation wicri:level="1"><country xml:lang="fr">Danemark</country>
<wicri:regionArea>Informatics and Mathematical Modelling, The Technical University of Denmark, DK-2800, Kongens Lyngby</wicri:regionArea>
<wicri:noRegion>Kongens Lyngby</wicri:noRegion>
</affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">Danemark</country>
</affiliation>
</author>
<author><name sortKey="Nielson, Hanne Riis" sort="Nielson, Hanne Riis" uniqKey="Nielson H" first="Hanne Riis" last="Nielson">Hanne Riis Nielson</name>
<affiliation wicri:level="1"><country xml:lang="fr">Danemark</country>
<wicri:regionArea>Informatics and Mathematical Modelling, The Technical University of Denmark, DK-2800, Kongens Lyngby</wicri:regionArea>
<wicri:noRegion>Kongens Lyngby</wicri:noRegion>
</affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">Danemark</country>
</affiliation>
</author>
<author><name sortKey="Seidl, Helmut" sort="Seidl, Helmut" uniqKey="Seidl H" first="Helmut" last="Seidl">Helmut Seidl</name>
<affiliation wicri:level="1"><country xml:lang="fr">Allemagne</country>
<wicri:regionArea>Fachbereich IV — Informatik, Universität Trier, D-54286, Trier</wicri:regionArea>
<wicri:noRegion>54286, Trier</wicri:noRegion>
<wicri:noRegion>Trier</wicri:noRegion>
</affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">Allemagne</country>
</affiliation>
</author>
</analytic>
<monogr></monogr>
<series><title level="s">Lecture Notes in Computer Science</title>
<imprint><date>2002</date>
</imprint>
<idno type="ISSN">0302-9743</idno>
<idno type="ISSN">0302-9743</idno>
</series>
<idno type="istex">EB7186CC090D19320A84864F0CB4065CC4B95D28</idno>
<idno type="DOI">10.1007/3-540-45927-8_18</idno>
<idno type="ChapterID">18</idno>
<idno type="ChapterID">Chap18</idno>
</biblStruct>
</sourceDesc>
<seriesStmt><idno type="ISSN">0302-9743</idno>
</seriesStmt>
</fileDesc>
<profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Asymptotic behavior</term>
<term>Automatic analysis</term>
<term>Horn clauses</term>
<term>Program analysis</term>
<term>Sparse matrix</term>
</keywords>
<keywords scheme="Pascal" xml:lang="fr"><term>Analyse automatique</term>
<term>Analyse programme</term>
<term>Clause Horn</term>
<term>Comportement asymptotique</term>
<term>Matrice creuse</term>
</keywords>
</textClass>
<langUsage><language ident="en">en</language>
</langUsage>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">Abstract: We consider the problem of automating the derivation of tight asymptotic complexity bounds for solving Horn clauses. Clearly, the solving time crucially depends on the “sparseness” of the computed relations. Therefore, our asymptotic runtime analysis is accompanied by an asymptotic sparsity calculus together with an asymptotic sparsity analysis. The technical problem here is that least fixpoint iteration fails on asymptotic complexity expressions: the intuitive reason is that O(1)+ srO(1) = O(1) but O(1) + ⋯ + O(1) may return any value.</div>
</front>
</TEI>
<double idat="0302-9743:2002:Nielson F:automatic:complexity:analysis"><INIST><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" level="a">Automatic complexity analysis</title>
<author><name sortKey="Nielson, Flemming" sort="Nielson, Flemming" uniqKey="Nielson F" first="Flemming" last="Nielson">Flemming Nielson</name>
<affiliation wicri:level="1"><inist:fA14 i1="01"><s1>Informatics and Mathematical Modelling, The Technical University of Denmark</s1>
<s2>2800 Kongens Lyngby</s2>
<s3>DNK</s3>
<sZ>1 aut.</sZ>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>Danemark</country>
<wicri:noRegion>2800 Kongens Lyngby</wicri:noRegion>
</affiliation>
</author>
<author><name sortKey="Nielson, Hanne Riis" sort="Nielson, Hanne Riis" uniqKey="Nielson H" first="Hanne Riis" last="Nielson">Hanne Riis Nielson</name>
<affiliation wicri:level="1"><inist:fA14 i1="01"><s1>Informatics and Mathematical Modelling, The Technical University of Denmark</s1>
<s2>2800 Kongens Lyngby</s2>
<s3>DNK</s3>
<sZ>1 aut.</sZ>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>Danemark</country>
<wicri:noRegion>2800 Kongens Lyngby</wicri:noRegion>
</affiliation>
</author>
<author><name sortKey="Seidl, Helmut" sort="Seidl, Helmut" uniqKey="Seidl H" first="Helmut" last="Seidl">Helmut Seidl</name>
<affiliation wicri:level="1"><inist:fA14 i1="02"><s1>Fachbereich IV - Informatik, Universität Trier</s1>
<s2>54286 Trier</s2>
<s3>DEU</s3>
<sZ>3 aut.</sZ>
</inist:fA14>
<country>Allemagne</country>
<wicri:noRegion>54286 Trier</wicri:noRegion>
<wicri:noRegion>Universität Trier</wicri:noRegion>
<wicri:noRegion>54286 Trier</wicri:noRegion>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">INIST</idno>
<idno type="inist">02-0318071</idno>
<date when="2002">2002</date>
<idno type="stanalyst">PASCAL 02-0318071 INIST</idno>
<idno type="RBID">Pascal:02-0318071</idno>
<idno type="wicri:Area/PascalFrancis/Corpus">000D48</idno>
<idno type="wicri:Area/PascalFrancis/Curation">000188</idno>
<idno type="wicri:Area/PascalFrancis/Checkpoint">000B22</idno>
<idno type="wicri:explorRef" wicri:stream="PascalFrancis" wicri:step="Checkpoint">000B22</idno>
<idno type="wicri:doubleKey">0302-9743:2002:Nielson F:automatic:complexity:analysis</idno>
<idno type="wicri:Area/Main/Merge">001F87</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en" level="a">Automatic complexity analysis</title>
<author><name sortKey="Nielson, Flemming" sort="Nielson, Flemming" uniqKey="Nielson F" first="Flemming" last="Nielson">Flemming Nielson</name>
<affiliation wicri:level="1"><inist:fA14 i1="01"><s1>Informatics and Mathematical Modelling, The Technical University of Denmark</s1>
<s2>2800 Kongens Lyngby</s2>
<s3>DNK</s3>
<sZ>1 aut.</sZ>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>Danemark</country>
<wicri:noRegion>2800 Kongens Lyngby</wicri:noRegion>
</affiliation>
</author>
<author><name sortKey="Nielson, Hanne Riis" sort="Nielson, Hanne Riis" uniqKey="Nielson H" first="Hanne Riis" last="Nielson">Hanne Riis Nielson</name>
<affiliation wicri:level="1"><inist:fA14 i1="01"><s1>Informatics and Mathematical Modelling, The Technical University of Denmark</s1>
<s2>2800 Kongens Lyngby</s2>
<s3>DNK</s3>
<sZ>1 aut.</sZ>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>Danemark</country>
<wicri:noRegion>2800 Kongens Lyngby</wicri:noRegion>
</affiliation>
</author>
<author><name sortKey="Seidl, Helmut" sort="Seidl, Helmut" uniqKey="Seidl H" first="Helmut" last="Seidl">Helmut Seidl</name>
<affiliation wicri:level="1"><inist:fA14 i1="02"><s1>Fachbereich IV - Informatik, Universität Trier</s1>
<s2>54286 Trier</s2>
<s3>DEU</s3>
<sZ>3 aut.</sZ>
</inist:fA14>
<country>Allemagne</country>
<wicri:noRegion>54286 Trier</wicri:noRegion>
<wicri:noRegion>Universität Trier</wicri:noRegion>
<wicri:noRegion>54286 Trier</wicri:noRegion>
</affiliation>
</author>
</analytic>
<series><title level="j" type="main">Lecture notes in computer science</title>
<idno type="ISSN">0302-9743</idno>
<imprint><date when="2002">2002</date>
</imprint>
</series>
</biblStruct>
</sourceDesc>
<seriesStmt><title level="j" type="main">Lecture notes in computer science</title>
<idno type="ISSN">0302-9743</idno>
</seriesStmt>
</fileDesc>
<profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Asymptotic behavior</term>
<term>Automatic analysis</term>
<term>Horn clauses</term>
<term>Program analysis</term>
<term>Sparse matrix</term>
</keywords>
<keywords scheme="Pascal" xml:lang="fr"><term>Clause Horn</term>
<term>Comportement asymptotique</term>
<term>Analyse automatique</term>
<term>Analyse programme</term>
<term>Matrice creuse</term>
</keywords>
</textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">We consider the problem of automating the derivation of tight asymptotic complexity bounds for solving Horn clauses. Clearly, the solving time crucially depends on the "sparseness" of the computed relations. Therefore, our asymptotic runtime analysis is accompanied by an asymptotic sparsity calculus together with an asymptotic sparsity analysis. The technical problem here is that least fixpoint iteration fails on asymptotic complexity expressions: the intuitive reason is that O(1)+ O(1) = O(1) but O(1) +...+ O(1) may return any value.</div>
</front>
</TEI>
</INIST>
<ISTEX><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Automatic Complexity Analysis</title>
<author><name sortKey="Nielson, Flemming" sort="Nielson, Flemming" uniqKey="Nielson F" first="Flemming" last="Nielson">Flemming Nielson</name>
</author>
<author><name sortKey="Nielson, Hanne Riis" sort="Nielson, Hanne Riis" uniqKey="Nielson H" first="Hanne Riis" last="Nielson">Hanne Riis Nielson</name>
</author>
<author><name sortKey="Seidl, Helmut" sort="Seidl, Helmut" uniqKey="Seidl H" first="Helmut" last="Seidl">Helmut Seidl</name>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">ISTEX</idno>
<idno type="RBID">ISTEX:EB7186CC090D19320A84864F0CB4065CC4B95D28</idno>
<date when="2002" year="2002">2002</date>
<idno type="doi">10.1007/3-540-45927-8_18</idno>
<idno type="url">https://api.istex.fr/document/EB7186CC090D19320A84864F0CB4065CC4B95D28/fulltext/pdf</idno>
<idno type="wicri:Area/Istex/Corpus">001112</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">001112</idno>
<idno type="wicri:Area/Istex/Curation">001001</idno>
<idno type="wicri:Area/Istex/Checkpoint">000B72</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">000B72</idno>
<idno type="wicri:doubleKey">0302-9743:2002:Nielson F:automatic:complexity:analysis</idno>
<idno type="wicri:Area/Main/Merge">001F12</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Automatic Complexity Analysis</title>
<author><name sortKey="Nielson, Flemming" sort="Nielson, Flemming" uniqKey="Nielson F" first="Flemming" last="Nielson">Flemming Nielson</name>
<affiliation wicri:level="1"><country xml:lang="fr">Danemark</country>
<wicri:regionArea>Informatics and Mathematical Modelling, The Technical University of Denmark, DK-2800, Kongens Lyngby</wicri:regionArea>
<wicri:noRegion>Kongens Lyngby</wicri:noRegion>
</affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">Danemark</country>
</affiliation>
</author>
<author><name sortKey="Nielson, Hanne Riis" sort="Nielson, Hanne Riis" uniqKey="Nielson H" first="Hanne Riis" last="Nielson">Hanne Riis Nielson</name>
<affiliation wicri:level="1"><country xml:lang="fr">Danemark</country>
<wicri:regionArea>Informatics and Mathematical Modelling, The Technical University of Denmark, DK-2800, Kongens Lyngby</wicri:regionArea>
<wicri:noRegion>Kongens Lyngby</wicri:noRegion>
</affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">Danemark</country>
</affiliation>
</author>
<author><name sortKey="Seidl, Helmut" sort="Seidl, Helmut" uniqKey="Seidl H" first="Helmut" last="Seidl">Helmut Seidl</name>
<affiliation wicri:level="1"><country xml:lang="fr">Allemagne</country>
<wicri:regionArea>Fachbereich IV — Informatik, Universität Trier, D-54286, Trier</wicri:regionArea>
<wicri:noRegion>54286, Trier</wicri:noRegion>
<wicri:noRegion>Trier</wicri:noRegion>
</affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">Allemagne</country>
</affiliation>
</author>
</analytic>
<monogr></monogr>
<series><title level="s">Lecture Notes in Computer Science</title>
<imprint><date>2002</date>
</imprint>
<idno type="ISSN">0302-9743</idno>
<idno type="ISSN">0302-9743</idno>
</series>
<idno type="istex">EB7186CC090D19320A84864F0CB4065CC4B95D28</idno>
<idno type="DOI">10.1007/3-540-45927-8_18</idno>
<idno type="ChapterID">18</idno>
<idno type="ChapterID">Chap18</idno>
</biblStruct>
</sourceDesc>
<seriesStmt><idno type="ISSN">0302-9743</idno>
</seriesStmt>
</fileDesc>
<profileDesc><textClass></textClass>
<langUsage><language ident="en">en</language>
</langUsage>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">Abstract: We consider the problem of automating the derivation of tight asymptotic complexity bounds for solving Horn clauses. Clearly, the solving time crucially depends on the “sparseness” of the computed relations. Therefore, our asymptotic runtime analysis is accompanied by an asymptotic sparsity calculus together with an asymptotic sparsity analysis. The technical problem here is that least fixpoint iteration fails on asymptotic complexity expressions: the intuitive reason is that O(1)+ srO(1) = O(1) but O(1) + ⋯ + O(1) may return any value.</div>
</front>
</TEI>
</ISTEX>
</double>
</record>
Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Rhénanie/explor/UnivTrevesV1/Data/Main/Curation
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 001C63 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Curation/biblio.hfd -nk 001C63 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien |wiki= Wicri/Rhénanie |area= UnivTrevesV1 |flux= Main |étape= Curation |type= RBID |clé= ISTEX:EB7186CC090D19320A84864F0CB4065CC4B95D28 |texte= Automatic Complexity Analysis }}
This area was generated with Dilib version V0.6.31. |