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
      0 references
      0 references
      1976
      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

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references
      0 references