UnivTrevesV1, PascalFrancis, Curation, bibRecord, 000115

Control-flow analysis in cubic time

Identifieur interne : 000115 ( PascalFrancis/Curation ); précédent : 000114; suivant : 000116

Control-flow analysis in cubic time

Auteurs : Flemming Nielson [Danemark] ; Helmut Seidl [Allemagne]

Source :

Lecture notes in computer science [ 0302-9743 ] ; 2001.

RBID : Pascal:01-0247617

Descripteurs français

Pascal (Inist)
- Commande écoulement, Méthode cas pire, Clause Horn, Instrument musique, Champ écoulement, Analyse temporelle, Orienté objet, Analyse programme, Pavage.

English descriptors

KwdEn :
- Flow control, Flow field, Horn clauses, Musical instrument, Object oriented, Program analysis, Tiling, Time analysis, Worst case method.

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⁵) to O(n³) in both cases.

A01	`01`	`1`		`@0 0302-9743`
A05				`@2 2028`
A08	`01`	`1`	`ENG`	`@1 Control-flow analysis in cubic time`
A09	`01`	`1`	`ENG`	`@1 Programming languages and systems : Genova, 2-6 April 2001`
A11	`01`	`1`		`@1 NIELSON (Flemming)`
A11	`02`	`1`		`@1 SEIDL (Helmut)`
A12	`01`	`1`		`@1 SANDS (David) @9 ed.`
A14	`01`			`@1 Computer Science Department, Aarhus University (Bldg. 540), Ny Munkegade @2 8000 Aarhus @3 DNK @Z 1 aut.`
A14	`02`			`@1 FB IV - Informatik, Universität Trier @2 54286 Trier @3 DEU @Z 2 aut.`
A20				`@1 252-268`
A21				`@1 2001`
A23	`01`			`@0 ENG`
A26	`01`			`@0 3-540-41862-8`
A43	`01`			`@1 INIST @2 16343 @5 354000092388340170`
A44				`@0 0000 @1 © 2001 INIST-CNRS. All rights reserved.`
A45				`@0 12 ref.`
A47	`01`	`1`		`@0 01-0247617`
A60				`@1 P @2 C`
A61				`@0 A`
A64	`01`	`1`		`@0 Lecture notes in computer science`
A66	`01`			`@0 DEU`
A66	`02`			`@0 USA`
C01	`01`		`ENG`	@0 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⁵) to O(n³) in both cases.
C02	`01`	`X`		`@0 001D02A02`
C03	`01`	`1`	`FRE`	`@0 Commande écoulement @5 01`
C03	`01`	`1`	`ENG`	`@0 Flow control @5 01`
C03	`02`	`X`	`FRE`	`@0 Méthode cas pire @5 02`
C03	`02`	`X`	`ENG`	`@0 Worst case method @5 02`
C03	`02`	`X`	`SPA`	`@0 Método caso peor @5 02`
C03	`03`	`3`	`FRE`	`@0 Clause Horn @5 03`
C03	`03`	`3`	`ENG`	`@0 Horn clauses @5 03`
C03	`04`	`X`	`FRE`	`@0 Instrument musique @5 04`
C03	`04`	`X`	`ENG`	`@0 Musical instrument @5 04`
C03	`04`	`X`	`SPA`	`@0 Instrumento musical @5 04`
C03	`05`	`X`	`FRE`	`@0 Champ écoulement @5 05`
C03	`05`	`X`	`ENG`	`@0 Flow field @5 05`
C03	`05`	`X`	`SPA`	`@0 Campo flujo @5 05`
C03	`06`	`X`	`FRE`	`@0 Analyse temporelle @5 06`
C03	`06`	`X`	`ENG`	`@0 Time analysis @5 06`
C03	`06`	`X`	`SPA`	`@0 Análisis temporal @5 06`
C03	`07`	`X`	`FRE`	`@0 Orienté objet @5 07`
C03	`07`	`X`	`ENG`	`@0 Object oriented @5 07`
C03	`07`	`X`	`SPA`	`@0 Orientado objeto @5 07`
C03	`08`	`X`	`FRE`	`@0 Analyse programme @5 08`
C03	`08`	`X`	`ENG`	`@0 Program analysis @5 08`
C03	`08`	`X`	`SPA`	`@0 Análisis programa @5 08`
C03	`09`	`X`	`FRE`	`@0 Pavage @5 09`
C03	`09`	`X`	`ENG`	`@0 Tiling @5 09`
N21				`@1 169`

A30	`01`	`1`	`ENG`	`@1 ESOP 2001 : European symposium on programming @2 10 @3 Genova ITA @4 2001-04-02`

Links toward previous steps (curation, corpus...)

to stream PascalFrancis, to step Corpus: Pour aller vers cette notice dans l'étape Curation :000E42

Links to Exploration step

Pascal:01-0247617

Le document en format XML

<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" level="a">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 wicri:level="1"><inist:fA14 i1="01"><s1>Computer Science Department, Aarhus University (Bldg. 540), Ny Munkegade</s1>
<s2>8000 Aarhus </s2>
<s3>DNK</s3>
<sZ>1 aut.</sZ>
</inist:fA14>
<country>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"><inist:fA14 i1="02"><s1>FB IV - Informatik, Universität Trier</s1>
<s2>54286 Trier</s2>
<s3>DEU</s3>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>Allemagne</country>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">INIST</idno>
<idno type="inist">01-0247617</idno>
<date when="2001">2001</date>
<idno type="stanalyst">PASCAL 01-0247617 INIST</idno>
<idno type="RBID">Pascal:01-0247617</idno>
<idno type="wicri:Area/PascalFrancis/Corpus">000E42</idno>
<idno type="wicri:Area/PascalFrancis/Curation">000115</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en" level="a">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 wicri:level="1"><inist:fA14 i1="01"><s1>Computer Science Department, Aarhus University (Bldg. 540), Ny Munkegade</s1>
<s2>8000 Aarhus </s2>
<s3>DNK</s3>
<sZ>1 aut.</sZ>
</inist:fA14>
<country>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"><inist:fA14 i1="02"><s1>FB IV - Informatik, Universität Trier</s1>
<s2>54286 Trier</s2>
<s3>DEU</s3>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>Allemagne</country>
</affiliation>
</author>
</analytic>
<series><title level="j" type="main">Lecture notes in computer science</title>
<idno type="ISSN">0302-9743</idno>
<imprint><date when="2001">2001</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>Flow control</term>
<term>Flow field</term>
<term>Horn clauses</term>
<term>Musical instrument</term>
<term>Object oriented</term>
<term>Program analysis</term>
<term>Tiling</term>
<term>Time analysis</term>
<term>Worst case method</term>
</keywords>
<keywords scheme="Pascal" xml:lang="fr"><term>Commande écoulement</term>
<term>Méthode cas pire</term>
<term>Clause Horn</term>
<term>Instrument musique</term>
<term>Champ écoulement</term>
<term>Analyse temporelle</term>
<term>Orienté objet</term>
<term>Analyse programme</term>
<term>Pavage</term>
</keywords>
</textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">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<sup>5</sup>
) to O(n<sup>3</sup>
) in both cases.</div>
</front>
</TEI>
<inist><standard h6="B"><pA><fA01 i1="01" i2="1"><s0>0302-9743</s0>
</fA01>
<fA05><s2>2028</s2>
</fA05>
<fA08 i1="01" i2="1" l="ENG"><s1>Control-flow analysis in cubic time</s1>
</fA08>
<fA09 i1="01" i2="1" l="ENG"><s1>Programming languages and systems : Genova, 2-6 April 2001</s1>
</fA09>
<fA11 i1="01" i2="1"><s1>NIELSON (Flemming)</s1>
</fA11>
<fA11 i1="02" i2="1"><s1>SEIDL (Helmut)</s1>
</fA11>
<fA12 i1="01" i2="1"><s1>SANDS (David)</s1>
<s9>ed.</s9>
</fA12>
<fA14 i1="01"><s1>Computer Science Department, Aarhus University (Bldg. 540), Ny Munkegade</s1>
<s2>8000 Aarhus </s2>
<s3>DNK</s3>
<sZ>1 aut.</sZ>
</fA14>
<fA14 i1="02"><s1>FB IV - Informatik, Universität Trier</s1>
<s2>54286 Trier</s2>
<s3>DEU</s3>
<sZ>2 aut.</sZ>
</fA14>
<fA20><s1>252-268</s1>
</fA20>
<fA21><s1>2001</s1>
</fA21>
<fA23 i1="01"><s0>ENG</s0>
</fA23>
<fA26 i1="01"><s0>3-540-41862-8</s0>
</fA26>
<fA43 i1="01"><s1>INIST</s1>
<s2>16343</s2>
<s5>354000092388340170</s5>
</fA43>
<fA44><s0>0000</s0>
<s1>© 2001 INIST-CNRS. All rights reserved.</s1>
</fA44>
<fA45><s0>12 ref.</s0>
</fA45>
<fA47 i1="01" i2="1"><s0>01-0247617</s0>
</fA47>
<fA60><s1>P</s1>
<s2>C</s2>
</fA60>
<fA61><s0>A</s0>
</fA61>
<fA64 i1="01" i2="1"><s0>Lecture notes in computer science</s0>
</fA64>
<fA66 i1="01"><s0>DEU</s0>
</fA66>
<fA66 i1="02"><s0>USA</s0>
</fA66>
<fC01 i1="01" l="ENG"><s0>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<sup>5</sup>
) to O(n<sup>3</sup>
) in both cases.</s0>
</fC01>
<fC02 i1="01" i2="X"><s0>001D02A02</s0>
</fC02>
<fC03 i1="01" i2="1" l="FRE"><s0>Commande écoulement</s0>
<s5>01</s5>
</fC03>
<fC03 i1="01" i2="1" l="ENG"><s0>Flow control</s0>
<s5>01</s5>
</fC03>
<fC03 i1="02" i2="X" l="FRE"><s0>Méthode cas pire</s0>
<s5>02</s5>
</fC03>
<fC03 i1="02" i2="X" l="ENG"><s0>Worst case method</s0>
<s5>02</s5>
</fC03>
<fC03 i1="02" i2="X" l="SPA"><s0>Método caso peor</s0>
<s5>02</s5>
</fC03>
<fC03 i1="03" i2="3" l="FRE"><s0>Clause Horn</s0>
<s5>03</s5>
</fC03>
<fC03 i1="03" i2="3" l="ENG"><s0>Horn clauses</s0>
<s5>03</s5>
</fC03>
<fC03 i1="04" i2="X" l="FRE"><s0>Instrument musique</s0>
<s5>04</s5>
</fC03>
<fC03 i1="04" i2="X" l="ENG"><s0>Musical instrument</s0>
<s5>04</s5>
</fC03>
<fC03 i1="04" i2="X" l="SPA"><s0>Instrumento musical</s0>
<s5>04</s5>
</fC03>
<fC03 i1="05" i2="X" l="FRE"><s0>Champ écoulement</s0>
<s5>05</s5>
</fC03>
<fC03 i1="05" i2="X" l="ENG"><s0>Flow field</s0>
<s5>05</s5>
</fC03>
<fC03 i1="05" i2="X" l="SPA"><s0>Campo flujo</s0>
<s5>05</s5>
</fC03>
<fC03 i1="06" i2="X" l="FRE"><s0>Analyse temporelle</s0>
<s5>06</s5>
</fC03>
<fC03 i1="06" i2="X" l="ENG"><s0>Time analysis</s0>
<s5>06</s5>
</fC03>
<fC03 i1="06" i2="X" l="SPA"><s0>Análisis temporal</s0>
<s5>06</s5>
</fC03>
<fC03 i1="07" i2="X" l="FRE"><s0>Orienté objet</s0>
<s5>07</s5>
</fC03>
<fC03 i1="07" i2="X" l="ENG"><s0>Object oriented</s0>
<s5>07</s5>
</fC03>
<fC03 i1="07" i2="X" l="SPA"><s0>Orientado objeto</s0>
<s5>07</s5>
</fC03>
<fC03 i1="08" i2="X" l="FRE"><s0>Analyse programme</s0>
<s5>08</s5>
</fC03>
<fC03 i1="08" i2="X" l="ENG"><s0>Program analysis</s0>
<s5>08</s5>
</fC03>
<fC03 i1="08" i2="X" l="SPA"><s0>Análisis programa</s0>
<s5>08</s5>
</fC03>
<fC03 i1="09" i2="X" l="FRE"><s0>Pavage</s0>
<s5>09</s5>
</fC03>
<fC03 i1="09" i2="X" l="ENG"><s0>Tiling</s0>
<s5>09</s5>
</fC03>
<fN21><s1>169</s1>
</fN21>
</pA>
<pR><fA30 i1="01" i2="1" l="ENG"><s1>ESOP 2001 : European symposium on programming</s1>
<s2>10</s2>
<s3>Genova ITA</s3>
<s4>2001-04-02</s4>
</fA30>
</pR>
</standard>
</inist>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Wicri/Rhénanie/explor/UnivTrevesV1/Data/PascalFrancis/Curation

HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000115 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/PascalFrancis/Curation/biblio.hfd -nk 000115 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Wicri/Rhénanie
   |area=    UnivTrevesV1
   |flux=    PascalFrancis
   |étape=   Curation
   |type=    RBID
   |clé=     Pascal:01-0247617
   |texte=   Control-flow analysis in cubic time
}}

This area was generated with Dilib version V0.6.31.
Data generation: Sat Jul 22 16:29:01 2017. Site generation: Wed Feb 28 14:55:37 2024

	Serveur d'exploration sur l'Université de Trèves
	Attention, ce site est en cours de développement ! Attention, site généré par des moyens informatiques à partir de corpus bruts. Les informations ne sont donc pas validées.

Serveur d'exploration sur l'Université de Trèves

Control-flow analysis in cubic time

Control-flow analysis in cubic time

Source :

Descripteurs français

English descriptors

Abstract

Links toward previous steps (curation, corpus...)

Links to Exploration step

Le document en format XML

Pour manipuler ce document sous Unix (Dilib)

Pour mettre un lien sur cette page dans le réseau Wicri