Program dependence graphs were introduced by Kuck as an intermediate program representation well suited for performing optimizations, vectorization, and parellelization. There are also additional applications for them as an internal program representation in program development environments.

In this paper we examine the issue of whether a program dependence graph is an adequate structure for representing a program's execution behavior. (This question has apparently never been addressed before in the literature.) We answer the question in the affirmative by showing that if the program dependence graphs of two programs are isomorphic then the programs are strongly equivalent.

(Click here to access the paper: PostScript, PDF.)