Node Listings for Reducible Flow Graphs

In [1], Kennedy conjectures that for every n node reducible flow graph, there is a sequence of nodes (with repetitions) of length O(n log n) such that all acyclic paths are subsequences thereof. Such a sequence would, if it could be found easily, enable one to do various kinds of global data flow analyses quickly. We show that for all reducible flow graphs such a sequence does exist, even if the number of edges is much larger than n . If the number of edges is O(n) , the node listing can be found in O(n log n) time.

Authors

• Alfred V. Aho
• Jeffrey D. Ullman

Keywords

No keywords are indexed for this paper.