A Fast and Usually Linear Algorithm for Global Flow Analysis (Q4091443)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3511581
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | A Fast and Usually Linear Algorithm for Global Flow Analysis |
scientific article; zbMATH DE number 3511581 |
Statements
A Fast and Usually Linear Algorithm for Global Flow Analysis (English)
0 references
1976
0 references
0.7590875029563904
0 references
0.7476518154144287
0 references
0.7360092997550964
0 references
to edges of the flow graph and belonging to the ``information propagation space'' defined by the author. The graph reduction algorithm description in a PASCAL-like language is preceded by some general considerations, proofs of some lemmas and theorems about the information propagation problem. Next, the time complexity (in number of function compositions and intersections) of this algorithm is analyzed both in general and for some special classes of program flow graphs. For a graph of \(e\) edges, the algorithm has a worst-case time bound of \(O(e \log e)\) function operations mentioned above. In programming terms, the number of operations is proportional to \(e\) plus the number of exits from program loops; consequently for ``well-structured'' programs linearity is guaranteed.
0 references