Program dependences are syntactic relationships between program statements, which are used in several areas of computer science to obtain "approximate" information about semantic relationships between statements. There are two basic types of program dependences: control dependences, which are features of a program's control structure, and data flow dependences, which are features of the placement of variable definitions and uses in a program. Typically, proposed uses of program dependences have been justified only informally, if at all. Since program dependences are used for such critical purposes as software testing, debugging, and maintenance, code optimization and parallelization, and computer security, this lack of rigor is unacceptable. This thesis presents the results of a rigorous investigation of the significance of program dependences for software testing, debugging, and maintenance. A concept called "semantic dependence" is defined, which is necessary condition for certain kinds of faults and modifications in a program statement to affect the execution behavior of other statements. Semantic dependence is defined by giving a semantics to a graph-theoretic program representation used to find program dependences. It is shown that a certain generalization of control and data flow dependence, called "weak syntactic dependence" is a necessary condition for semantic dependence. It is shown that a commonly used generalization of control and data flow dependence, which we call "strong syntactic dependence", is not a necessary condition for semantic dependence, although it is a necessary condition for a restricted form, called "finitely demonstrated semantic dependence". It is shown that neither weak syntactic, strong syntactic, nor data flow dependence is a sufficient condition for semantic dependence. Together, these results allow a better evaluation of the soundness of some proposed uses of program dependences in testing, debugging, and maintenance. The results support some uses, controvert others, and suggest new ones. Finally, this thesis clarifies the concept of control dependence, which is described somewhat vaguely in the literature, via the results described above and via several graph theoretic characterizations of control dependence.
