Control-Flow Analysis in Cubic Time
Identifieur interne : 001185 ( Istex/Corpus ); précédent : 001184; suivant : 001186Control-Flow Analysis in Cubic Time
Auteurs : Flemming Nielson ; Helmut SeidlSource :
- Lecture Notes in Computer Science [ 0302-9743 ] ; 2001.
Abstract
Abstract: It is well-known that context-independent control flow analysis can be performed in cubic time for functional and object-oriented languages. Yet recent applications of control flow analysis to calculi of computation (like the π-calculus and the ambient calculus) have reported considerably higher complexities. In this paper we introduce two general techniques, the use of Horn clauses with sharing and the use of tiling of Horn clauses, for reducing the worst-case complexity of analyses. Applying these techniques to the π-calculus and the ambient calculus we reduce the complexity from O(n 5) to O(n 3) in both cases.
Url:
DOI: 10.1007/3-540-45309-1_17
Links to Exploration step
ISTEX:D42CAB5F9BF46B05D6F00A8FDD9F10633AF967DBLe document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Control-Flow Analysis in Cubic Time</title><author><name sortKey="Nielson, Flemming" sort="Nielson, Flemming" uniqKey="Nielson F" first="Flemming" last="Nielson">Flemming Nielson</name><affiliation><mods:affiliation>Computer Science Department, Aarhus University, (Bldg. 540) Ny Munkegade, DK-8000, cAarhus C, Denmark</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: fn@daimi.au.dk</mods:affiliation></affiliation></author><author><name sortKey="Seidl, Helmut" sort="Seidl, Helmut" uniqKey="Seidl H" first="Helmut" last="Seidl">Helmut Seidl</name><affiliation><mods:affiliation>FB IV ― Informatik, Universität Trier, D-54286, Trier, Germany</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: seidl@uni-trier.de</mods:affiliation></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:D42CAB5F9BF46B05D6F00A8FDD9F10633AF967DB</idno><date when="2001" year="2001">2001</date><idno type="doi">10.1007/3-540-45309-1_17</idno><idno type="url">https://api.istex.fr/document/D42CAB5F9BF46B05D6F00A8FDD9F10633AF967DB/fulltext/pdf</idno><idno type="wicri:Area/Istex/Corpus">001185</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">001185</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Control-Flow Analysis in Cubic Time</title><author><name sortKey="Nielson, Flemming" sort="Nielson, Flemming" uniqKey="Nielson F" first="Flemming" last="Nielson">Flemming Nielson</name><affiliation><mods:affiliation>Computer Science Department, Aarhus University, (Bldg. 540) Ny Munkegade, DK-8000, cAarhus C, Denmark</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: fn@daimi.au.dk</mods:affiliation></affiliation></author><author><name sortKey="Seidl, Helmut" sort="Seidl, Helmut" uniqKey="Seidl H" first="Helmut" last="Seidl">Helmut Seidl</name><affiliation><mods:affiliation>FB IV ― Informatik, Universität Trier, D-54286, Trier, Germany</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: seidl@uni-trier.de</mods:affiliation></affiliation></author></analytic><monogr></monogr><series><title level="s">Lecture Notes in Computer Science</title><imprint><date>2001</date></imprint><idno type="ISSN">0302-9743</idno><idno type="ISSN">0302-9743</idno></series><idno type="istex">D42CAB5F9BF46B05D6F00A8FDD9F10633AF967DB</idno><idno type="DOI">10.1007/3-540-45309-1_17</idno><idno type="ChapterID">17</idno><idno type="ChapterID">Chap17</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: It is well-known that context-independent control flow analysis can be performed in cubic time for functional and object-oriented languages. Yet recent applications of control flow analysis to calculi of computation (like the π-calculus and the ambient calculus) have reported considerably higher complexities. In this paper we introduce two general techniques, the use of Horn clauses with sharing and the use of tiling of Horn clauses, for reducing the worst-case complexity of analyses. Applying these techniques to the π-calculus and the ambient calculus we reduce the complexity from O(n 5) to O(n 3) in both cases.</div></front></TEI><istex><corpusName>springer</corpusName><author><json:item><name>Flemming Nielson</name><affiliations><json:string>Computer Science Department, Aarhus University, (Bldg. 540) Ny Munkegade, DK-8000, cAarhus C, Denmark</json:string><json:string>E-mail: fn@daimi.au.dk</json:string></affiliations></json:item><json:item><name>Helmut Seidl</name><affiliations><json:string>FB IV ― Informatik, Universität Trier, D-54286, Trier, Germany</json:string><json:string>E-mail: seidl@uni-trier.de</json:string></affiliations></json:item></author><language><json:string>eng</json:string></language><originalGenre><json:string>OriginalPaper</json:string></originalGenre><abstract>Abstract: It is well-known that context-independent control flow analysis can be performed in cubic time for functional and object-oriented languages. Yet recent applications of control flow analysis to calculi of computation (like the π-calculus and the ambient calculus) have reported considerably higher complexities. In this paper we introduce two general techniques, the use of Horn clauses with sharing and the use of tiling of Horn clauses, for reducing the worst-case complexity of analyses. Applying these techniques to the π-calculus and the ambient calculus we reduce the complexity from O(n 5) to O(n 3) in both cases.</abstract><qualityIndicators><score>6.152</score><pdfVersion>1.3</pdfVersion><pdfPageSize>430 x 650 pts</pdfPageSize><refBibsNative>false</refBibsNative><keywordCount>0</keywordCount><abstractCharCount>630</abstractCharCount><pdfWordCount>7536</pdfWordCount><pdfCharCount>33507</pdfCharCount><pdfPageCount>17</pdfPageCount><abstractWordCount>96</abstractWordCount></qualityIndicators><title>Control-Flow Analysis in Cubic Time</title><chapterId><json:string>17</json:string><json:string>Chap17</json:string></chapterId><refBibs><json:item><author><json:item><name>A Aiken</name></json:item></author><host><volume>35</volume><pages><last>111</last><first>79</first></pages><author></author><title>Science of Computer Programming</title><publicationDate>1999</publicationDate></host><title>Introduction to set constraint-based program analysis</title><publicationDate>1999</publicationDate></json:item><json:item><author><json:item><name>C Bodei</name></json:item><json:item><name>P Degano</name></json:item><json:item><name>F Nielson</name></json:item><json:item><name>H. Riis Nielson</name></json:item></author><host><author></author><title>Information and Computation</title><publicationDate>2001</publicationDate></host><title>Static analysis for the πcalculus with applications to security</title><publicationDate>2001</publicationDate></json:item><json:item><author><json:item><name>C Bodei</name></json:item><json:item><name>P Degano</name></json:item><json:item><name>F Nielson</name></json:item><json:item><name>H. Riis Nielson</name></json:item></author><host><pages><last>98</last><first>84</first></pages><author></author><title>Proceedings of CONCUR'98</title></host><title>Control flow analysis for the π-calculus</title></json:item><json:item><author><json:item><name>L Cardelli</name></json:item><json:item><name>A,D Gordon</name></json:item></author><host><pages><last>155</last><first>140</first></pages><author></author><title>Proceedings of FoSSaCS'98</title><publicationDate>1998</publicationDate></host><title>Mobile ambients</title><publicationDate>1998</publicationDate></json:item><json:item><author><json:item><name>W,F Dowling</name></json:item><json:item><name>J,H Gallier</name></json:item></author><host><volume>3</volume><pages><last>284</last><first>267</first></pages><author></author><title>Journal of Logic Programming</title><publicationDate>1984</publicationDate></host><title>Linear-time algorithms for testing the satisfiability of propositional Horn formulae</title><publicationDate>1984</publicationDate></json:item><json:item><host><pages><last>631</last><first>525</first></pages><author><json:item><name>J Van Leeuwen</name></json:item></author><title>Graph Algorithms. Handbook of Theoretical Computer Science</title><publicationDate>1990</publicationDate></host></json:item><json:item><author><json:item><name>D Mcallester</name></json:item></author><host><pages><last>329</last><first>312</first></pages><author></author><title>6th Static Analysis Symposium (SAS)</title><publicationDate>1999</publicationDate></host><title>On the complexity analysis of static analyses</title><publicationDate>1999</publicationDate></json:item><json:item><host><pages><last>77</last><first>1</first></pages><author><json:item><name>R Milner</name></json:item><json:item><name>J Parrow</name></json:item><json:item><name>D Walker</name></json:item></author><title>A calculus of mobile processes (I and II) Information and Computation</title><publicationDate>1992</publicationDate></host></json:item><json:item><host><author><json:item><name>F Nielson</name></json:item><json:item><name>H Nielson</name></json:item><json:item><name>C,L Hankin</name></json:item></author><title>Principles of Program Analysis</title><publicationDate>1999</publicationDate></host></json:item><json:item><author><json:item><name>F Nielson</name></json:item><json:item><name>H Nielson</name></json:item><json:item><name>R,R Hansen</name></json:item><json:item><name>J,G Jensen</name></json:item></author><host><pages><last>477</last><first>463</first></pages><author></author><title>Proceedings of CONCUR'99</title><publicationDate>1999</publicationDate></host><title>Validating firewalls in mobile ambients</title><publicationDate>1999</publicationDate></json:item><json:item><author><json:item><name>J Rehof</name></json:item><json:item><name>T Mogensen</name></json:item></author><host><volume>35</volume><pages><last>221</last><first>191</first></pages><issue>1</issue><author></author><title>Science of Computer Programming</title><publicationDate>1999</publicationDate></host><title>Tractable constraints in finite semilattices</title><publicationDate>1999</publicationDate></json:item><json:item><author><json:item><name>M Yannakakis</name></json:item></author><host><pages><last>242</last><first>230</first></pages><author></author><title>9th ACM Symp. on Principles of Database Systems (PODS)</title><publicationDate>1990</publicationDate></host><title>Graph-theoretic concepts in database theory</title><publicationDate>1990</publicationDate></json:item></refBibs><genre><json:string>conference</json:string></genre><serie><editor><json:item><name>Gerhard Goos</name><affiliations><json:string>Karlsruhe University, Germany</json:string></affiliations></json:item><json:item><name>Juris Hartmanis</name><affiliations><json:string>Cornell University, NY, USA</json:string></affiliations></json:item><json:item><name>Jan van Leeuwen</name><affiliations><json:string>Utrecht University, The Netherlands</json:string></affiliations></json:item></editor><issn><json:string>0302-9743</json:string></issn><language><json:string>unknown</json:string></language><title>Lecture Notes in Computer Science</title><copyrightDate>2001</copyrightDate></serie><host><editor><json:item><name>David Sands</name><affiliations><json:string>Department of Computing Science, Chalmers University of Technology and Göteborg University, 412 96, Göteborg, Sweden</json:string><json:string>E-mail: dave@cs.chalmers.se</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>Programming Languages, Compilers, Interpreters</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><isbn><json:string>978-3-540-41862-7</json:string></isbn><language><json:string>unknown</json:string></language><title>Programming Languages and Systems</title><bookId><json:string>3-540-45309-1</json:string></bookId><volume>2028</volume><pages><last>268</last><first>252</first></pages><issn><json:string>0302-9743</json:string></issn><genre><json:string>book-series</json:string></genre><eisbn><json:string>978-3-540-45309-3</json:string></eisbn><copyrightDate>2001</copyrightDate><doi><json:string>10.1007/3-540-45309-1</json:string></doi></host><publicationDate>2001</publicationDate><copyrightDate>2001</copyrightDate><doi><json:string>10.1007/3-540-45309-1_17</json:string></doi><id>D42CAB5F9BF46B05D6F00A8FDD9F10633AF967DB</id><score>0.3831391</score><fulltext><json:item><extension>pdf</extension><original>true</original><mimetype>application/pdf</mimetype><uri>https://api.istex.fr/document/D42CAB5F9BF46B05D6F00A8FDD9F10633AF967DB/fulltext/pdf</uri></json:item><json:item><extension>zip</extension><original>false</original><mimetype>application/zip</mimetype><uri>https://api.istex.fr/document/D42CAB5F9BF46B05D6F00A8FDD9F10633AF967DB/fulltext/zip</uri></json:item><istex:fulltextTEI uri="https://api.istex.fr/document/D42CAB5F9BF46B05D6F00A8FDD9F10633AF967DB/fulltext/tei"><teiHeader><fileDesc><titleStmt><title level="a" type="main" xml:lang="en">Control-Flow Analysis in Cubic Time</title><respStmt><resp>Références bibliographiques récupérées via GROBID</resp><name resp="ISTEX-API">ISTEX-API (INIST-CNRS)</name></respStmt><respStmt><resp>Références bibliographiques récupérées via GROBID</resp><name resp="ISTEX-API">ISTEX-API (INIST-CNRS)</name></respStmt></titleStmt><publicationStmt><authority>ISTEX</authority><publisher>Springer Berlin Heidelberg</publisher><pubPlace>Berlin, Heidelberg</pubPlace><availability><p>Springer-Verlag Berlin Heidelberg, 2001</p></availability><date>2001</date></publicationStmt><sourceDesc><biblStruct type="inbook"><analytic><title level="a" type="main" xml:lang="en">Control-Flow Analysis in Cubic Time</title><author xml:id="author-1"><persName><forename type="first">Flemming</forename><surname>Nielson</surname></persName><email>fn@daimi.au.dk</email><affiliation>Computer Science Department, Aarhus University, (Bldg. 540) Ny Munkegade, DK-8000, cAarhus C, Denmark</affiliation></author><author xml:id="author-2"><persName><forename type="first">Helmut</forename><surname>Seidl</surname></persName><email>seidl@uni-trier.de</email><affiliation>FB IV ― Informatik, Universität Trier, D-54286, Trier, Germany</affiliation></author></analytic><monogr><title level="m">Programming Languages and Systems</title><title level="m" type="sub">10th European Symposium on Programming, ESOP 2001 Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2001 Genova, Italy, April 2–6, 2001 Proceedings</title><idno type="pISBN">978-3-540-41862-7</idno><idno type="eISBN">978-3-540-45309-3</idno><idno type="pISSN">0302-9743</idno><idno type="DOI">10.1007/3-540-45309-1</idno><idno type="book-ID">3-540-45309-1</idno><idno type="book-title-ID">67003</idno><idno type="book-sequence-number">2028</idno><idno type="book-volume-number">2028</idno><idno type="book-chapter-count">28</idno><editor><persName><forename type="first">David</forename><surname>Sands</surname></persName><email>dave@cs.chalmers.se</email><affiliation>Department of Computing Science, Chalmers University of Technology and Göteborg University, 412 96, Göteborg, Sweden</affiliation></editor><imprint><publisher>Springer Berlin Heidelberg</publisher><pubPlace>Berlin, Heidelberg</pubPlace><date type="published" when="2001-03-23"></date><biblScope unit="volume">2028</biblScope><biblScope unit="page" from="252">252</biblScope><biblScope unit="page" to="268">268</biblScope></imprint></monogr><series><title level="s">Lecture Notes in Computer Science</title><editor><persName><forename type="first">Gerhard</forename><surname>Goos</surname></persName><affiliation>Karlsruhe University, Germany</affiliation></editor><editor><persName><forename type="first">Juris</forename><surname>Hartmanis</surname></persName><affiliation>Cornell University, NY, USA</affiliation></editor><editor><persName><forename type="first">Jan</forename><surname>van Leeuwen</surname></persName><affiliation>Utrecht University, The Netherlands</affiliation></editor><biblScope><date>2001</date></biblScope><idno type="pISSN">0302-9743</idno><idno type="series-Id">558</idno></series><idno type="istex">D42CAB5F9BF46B05D6F00A8FDD9F10633AF967DB</idno><idno type="DOI">10.1007/3-540-45309-1_17</idno><idno type="ChapterID">17</idno><idno type="ChapterID">Chap17</idno></biblStruct></sourceDesc></fileDesc><profileDesc><creation><date>2001</date></creation><langUsage><language ident="en">en</language></langUsage><abstract xml:lang="en"><p>Abstract: It is well-known that context-independent control flow analysis can be performed in cubic time for functional and object-oriented languages. Yet recent applications of control flow analysis to calculi of computation (like the π-calculus and the ambient calculus) have reported considerably higher complexities. In this paper we introduce two general techniques, the use of Horn clauses with sharing and the use of tiling of Horn clauses, for reducing the worst-case complexity of analyses. Applying these techniques to the π-calculus and the ambient calculus we reduce the complexity from O(n 5) to O(n 3) in both cases.</p></abstract><textClass><keywords scheme="Book-Subject-Collection"><list><label>SUCO11645</label><item><term>Computer Science</term></item></list></keywords></textClass><textClass><keywords scheme="Book-Subject-Group"><list><label>I</label><label>I14037</label><label>I14010</label><label>I14029</label><label>I1603X</label><label>I16048</label><item><term>Computer Science</term></item><item><term>Programming Languages, Compilers, Interpreters</term></item><item><term>Programming Techniques</term></item><item><term>Software Engineering</term></item><item><term>Logics and Meanings of Programs</term></item><item><term>Mathematical Logic and Formal Languages</term></item></list></keywords></textClass></profileDesc><revisionDesc><change when="2001-03-23">Published</change><change xml:id="refBibs-istex" who="#ISTEX-API" when="2016-11-22">References added</change><change xml:id="refBibs-istex" who="#ISTEX-API" when="2017-01-20">References added</change></revisionDesc></teiHeader></istex:fulltextTEI><json:item><extension>txt</extension><original>false</original><mimetype>text/plain</mimetype><uri>https://api.istex.fr/document/D42CAB5F9BF46B05D6F00A8FDD9F10633AF967DB/fulltext/txt</uri></json:item></fulltext><metadata><istex:metadataXml wicri:clean="Springer, Publisher 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><SeriesTitle Language="En">Lecture Notes in Computer Science</SeriesTitle></SeriesInfo><SeriesHeader><EditorGroup><Editor AffiliationIDS="Aff1"><EditorName DisplayOrder="Western"><GivenName>Gerhard</GivenName><FamilyName>Goos</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff2"><EditorName DisplayOrder="Western"><GivenName>Juris</GivenName><FamilyName>Hartmanis</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff3"><EditorName DisplayOrder="Western"><GivenName>Jan</GivenName><Particle>van</Particle><FamilyName>Leeuwen</FamilyName></EditorName></Editor><Affiliation ID="Aff1"><OrgName>Karlsruhe University</OrgName><OrgAddress><Country>Germany</Country></OrgAddress></Affiliation><Affiliation ID="Aff2"><OrgName>Cornell University</OrgName><OrgAddress><State>NY</State><Country>USA</Country></OrgAddress></Affiliation><Affiliation ID="Aff3"><OrgName>Utrecht University</OrgName><OrgAddress><Country>The Netherlands</Country></OrgAddress></Affiliation></EditorGroup></SeriesHeader><Book Language="En"><BookInfo BookProductType="Proceedings" ContainsESM="No" Language="En" MediaType="eBook" NumberingStyle="Unnumbered" TocLevels="0"><BookID>3-540-45309-1</BookID><BookTitle>Programming Languages and Systems</BookTitle><BookSubTitle>10th European Symposium on Programming, ESOP 2001 Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2001 Genova, Italy, April 2–6, 2001 Proceedings</BookSubTitle><BookVolumeNumber>2028</BookVolumeNumber><BookSequenceNumber>2028</BookSequenceNumber><BookDOI>10.1007/3-540-45309-1</BookDOI><BookTitleID>67003</BookTitleID><BookPrintISBN>978-3-540-41862-7</BookPrintISBN><BookElectronicISBN>978-3-540-45309-3</BookElectronicISBN><BookChapterCount>28</BookChapterCount><BookHistory><OnlineDate><Year>2001</Year><Month>3</Month><Day>23</Day></OnlineDate></BookHistory><BookCopyright><CopyrightHolderName>Springer-Verlag Berlin Heidelberg</CopyrightHolderName><CopyrightYear>2001</CopyrightYear></BookCopyright><BookSubjectGroup><BookSubject Code="I" Type="Primary">Computer Science</BookSubject><BookSubject Code="I14037" Priority="1" Type="Secondary">Programming Languages, Compilers, Interpreters</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><BookContext><SeriesID>558</SeriesID></BookContext></BookInfo><BookHeader><EditorGroup><Editor AffiliationIDS="Aff4"><EditorName DisplayOrder="Western"><GivenName>David</GivenName><FamilyName>Sands</FamilyName></EditorName><Contact><Email>dave@cs.chalmers.se</Email></Contact></Editor><Affiliation ID="Aff4"><OrgDivision>Department of Computing Science</OrgDivision><OrgName>Chalmers University of Technology and Göteborg University</OrgName><OrgAddress><Postcode>412 96</Postcode><City>Göteborg</City><Country>Sweden</Country></OrgAddress></Affiliation></EditorGroup></BookHeader><Chapter ID="Chap17" Language="En"><ChapterInfo ChapterType="OriginalPaper" ContainsESM="No" Language="En" NumberingStyle="Unnumbered" TocLevels="0"><ChapterID>17</ChapterID><ChapterDOI>10.1007/3-540-45309-1_17</ChapterDOI><ChapterSequenceNumber>17</ChapterSequenceNumber><ChapterTitle Language="En">Control-Flow Analysis in Cubic Time</ChapterTitle><ChapterFirstPage>252</ChapterFirstPage><ChapterLastPage>268</ChapterLastPage><ChapterCopyright><CopyrightHolderName>Springer-Verlag Berlin Heidelberg</CopyrightHolderName><CopyrightYear>2001</CopyrightYear></ChapterCopyright><ChapterHistory><RegistrationDate><Year>2001</Year><Month>3</Month><Day>22</Day></RegistrationDate><OnlineDate><Year>2001</Year><Month>3</Month><Day>23</Day></OnlineDate></ChapterHistory><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><BookID>3-540-45309-1</BookID><BookTitle>Programming Languages and Systems</BookTitle></ChapterContext></ChapterInfo><ChapterHeader><AuthorGroup><Author AffiliationIDS="Aff5"><AuthorName DisplayOrder="Western"><GivenName>Flemming</GivenName><FamilyName>Nielson</FamilyName></AuthorName><Contact><Email>fn@daimi.au.dk</Email></Contact></Author><Author AffiliationIDS="Aff6"><AuthorName DisplayOrder="Western"><GivenName>Helmut</GivenName><FamilyName>Seidl</FamilyName></AuthorName><Contact><Email>seidl@uni-trier.de</Email></Contact></Author><Affiliation ID="Aff5"><OrgDivision>Computer Science Department</OrgDivision><OrgName>Aarhus University</OrgName><OrgAddress><Street>(Bldg. 540) Ny Munkegade</Street><Postcode>DK-8000</Postcode><City>cAarhus C</City><Country>Denmark</Country></OrgAddress></Affiliation><Affiliation ID="Aff6"><OrgDivision>FB IV ― Informatik</OrgDivision><OrgName>Universität Trier</OrgName><OrgAddress><Postcode>D-54286</Postcode><City>Trier</City><Country>Germany</Country></OrgAddress></Affiliation></AuthorGroup><Abstract ID="Abs1" Language="En"><Heading>Abstract</Heading><Para>It is well-known that context-independent control flow analysis can be performed in cubic time for functional and object-oriented languages. Yet recent applications of control flow analysis to calculi of computation (like the <Emphasis Type="Italic">π</Emphasis>-calculus and the ambient calculus) have reported considerably higher complexities. In this paper we introduce two general techniques, the use of <Emphasis Type="Italic">Horn clauses with sharing</Emphasis> and the use of <Emphasis Type="Italic">tiling of Horn clauses</Emphasis>, for reducing the worst-case complexity of analyses. Applying these techniques to the <Emphasis Type="Italic">π</Emphasis>-calculus and the ambient calculus we reduce the complexity from <Emphasis Type="Italic">O</Emphasis>(<Emphasis Type="Italic">n</Emphasis><Superscript>5</Superscript>) to <Emphasis Type="Italic">O</Emphasis>(<Emphasis Type="Italic">n</Emphasis><Superscript>3</Superscript>) in both cases.</Para></Abstract><KeywordGroup Language="En"><Heading>Keyword</Heading><Keyword>Program analysis</Keyword><Keyword>Horn clauses with sharing</Keyword><Keyword>tiling of Horn clauses</Keyword><Keyword><Emphasis Type="Italic">π</Emphasis>-calculus</Keyword><Keyword>ambient calculus</Keyword><Keyword>0-CFA</Keyword></KeywordGroup></ChapterHeader><NoBody></NoBody></Chapter></Book></Series></Publisher></istex:document></istex:metadataXml><mods version="3.6"><titleInfo lang="en"><title>Control-Flow Analysis in Cubic Time</title></titleInfo><titleInfo type="alternative" contentType="CDATA" lang="en"><title>Control-Flow Analysis in Cubic Time</title></titleInfo><name type="personal"><namePart type="given">Flemming</namePart><namePart type="family">Nielson</namePart><affiliation>Computer Science Department, Aarhus University, (Bldg. 540) Ny Munkegade, DK-8000, cAarhus C, Denmark</affiliation><affiliation>E-mail: fn@daimi.au.dk</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">Helmut</namePart><namePart type="family">Seidl</namePart><affiliation>FB IV ― Informatik, Universität Trier, D-54286, Trier, Germany</affiliation><affiliation>E-mail: seidl@uni-trier.de</affiliation><role><roleTerm type="text">author</roleTerm></role></name><typeOfResource>text</typeOfResource><genre type="conference" displayLabel="OriginalPaper"></genre><originInfo><publisher>Springer Berlin Heidelberg</publisher><place><placeTerm type="text">Berlin, Heidelberg</placeTerm></place><dateIssued encoding="w3cdtf">2001-03-23</dateIssued><copyrightDate encoding="w3cdtf">2001</copyrightDate></originInfo><language><languageTerm type="code" authority="rfc3066">en</languageTerm><languageTerm type="code" authority="iso639-2b">eng</languageTerm></language><physicalDescription><internetMediaType>text/html</internetMediaType></physicalDescription><abstract lang="en">Abstract: It is well-known that context-independent control flow analysis can be performed in cubic time for functional and object-oriented languages. Yet recent applications of control flow analysis to calculi of computation (like the π-calculus and the ambient calculus) have reported considerably higher complexities. In this paper we introduce two general techniques, the use of Horn clauses with sharing and the use of tiling of Horn clauses, for reducing the worst-case complexity of analyses. Applying these techniques to the π-calculus and the ambient calculus we reduce the complexity from O(n 5) to O(n 3) in both cases.</abstract><relatedItem type="host"><titleInfo><title>Programming Languages and Systems</title><subTitle>10th European Symposium on Programming, ESOP 2001 Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2001 Genova, Italy, April 2–6, 2001 Proceedings</subTitle></titleInfo><name type="personal"><namePart type="given">David</namePart><namePart type="family">Sands</namePart><affiliation>Department of Computing Science, Chalmers University of Technology and Göteborg University, 412 96, Göteborg, Sweden</affiliation><affiliation>E-mail: dave@cs.chalmers.se</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><genre type="book-series" displayLabel="Proceedings"></genre><originInfo><copyrightDate encoding="w3cdtf">2001</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="I14037">Programming Languages, Compilers, Interpreters</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/3-540-45309-1</identifier><identifier type="ISBN">978-3-540-41862-7</identifier><identifier type="eISBN">978-3-540-45309-3</identifier><identifier type="ISSN">0302-9743</identifier><identifier type="BookTitleID">67003</identifier><identifier type="BookID">3-540-45309-1</identifier><identifier type="BookChapterCount">28</identifier><identifier type="BookVolumeNumber">2028</identifier><identifier type="BookSequenceNumber">2028</identifier><part><date>2001</date><detail type="volume"><number>2028</number><caption>vol.</caption></detail><extent unit="pages"><start>252</start><end>268</end></extent></part><recordInfo><recordOrigin>Springer-Verlag Berlin Heidelberg, 2001</recordOrigin></recordInfo></relatedItem><relatedItem type="series"><titleInfo><title>Lecture Notes in Computer Science</title></titleInfo><name type="personal"><namePart type="given">Gerhard</namePart><namePart type="family">Goos</namePart><affiliation>Karlsruhe University, Germany</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Juris</namePart><namePart type="family">Hartmanis</namePart><affiliation>Cornell University, NY, USA</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Jan</namePart><namePart type="family">van Leeuwen</namePart><affiliation>Utrecht University, The Netherlands</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><originInfo><copyrightDate encoding="w3cdtf">2001</copyrightDate><issuance>serial</issuance></originInfo><identifier type="ISSN">0302-9743</identifier><identifier type="SeriesID">558</identifier><recordInfo><recordOrigin>Springer-Verlag Berlin Heidelberg, 2001</recordOrigin></recordInfo></relatedItem><identifier type="istex">D42CAB5F9BF46B05D6F00A8FDD9F10633AF967DB</identifier><identifier type="DOI">10.1007/3-540-45309-1_17</identifier><identifier type="ChapterID">17</identifier><identifier type="ChapterID">Chap17</identifier><accessCondition type="use and reproduction" contentType="copyright">Springer-Verlag Berlin Heidelberg, 2001</accessCondition><recordInfo><recordContentSource>SPRINGER</recordContentSource><recordOrigin>Springer-Verlag Berlin Heidelberg, 2001</recordOrigin></recordInfo></mods></metadata></istex></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Rhénanie/explor/UnivTrevesV1/Data/Istex/Corpus
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 001185 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Corpus/biblio.hfd -nk 001185 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Rhénanie
|area= UnivTrevesV1
|flux= Istex
|étape= Corpus
|type= RBID
|clé= ISTEX:D42CAB5F9BF46B05D6F00A8FDD9F10633AF967DB
|texte= Control-Flow Analysis in Cubic Time
}}
| This area was generated with Dilib version V0.6.31. |  |