An alternative characterization of weak order dependence. (English) Zbl 1379.68091

Summary: Control dependence forms the basis for many program analyses, such as program slicing. Recent work on control dependence analysis has led to new definitions of dependence that can allow for reactive programs with their necessarily non-terminating computations. One important such definition is the definition of Weak Order Dependence, which was introduced to generalize classical control dependence for a Control Flow Graph (CFG) without end nodes. In this paper we show that for a CFG where all nodes are reachable from each other, weak order dependence can be expressed in terms of traditional control dependence where one node has been converted into an end node.


68N30 Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.)


Full Text: DOI


[1] Amtoft, T., Slicing for modern program structures: a theory for eliminating irrelevant loops, Information Processing Letters, 106, 2, 45-51 (2008) · Zbl 1186.68120
[3] Binkley, D. W., The application of program slicing to regression testing, Information and Software Technology, 40, 11-12, 583-594 (1998)
[4] Binkley, D. W.; Horwitz, S.; Reps, T., Program integration for languages with procedure calls, ACM Transactions on Software Engineering and Methodology, 4, 1, 3-35 (1995)
[5] Black, S. E., Computing ripple effect for software maintenance, Journal of Software Maintenance and Evolution: Research and Practice, 13, 263-279 (2001) · Zbl 0971.68573
[6] Canfora, G.; Cimitile, A.; De Lucia, A., Conditioned program slicing, Information and Software Technology (Special Issue on Program Slicing), 40, 11-12, 595-607 (1998)
[7] Denning, D. E.; Denning, P. J., Certification of programs for secure information flow, Communications of the ACM, 20, 7, 504-513 (1977) · Zbl 0361.68033
[8] Ferrante, J.; Ottenstein, K. J.; Warren, J. D., The program dependence graph and its use in optimization, ACM Transactions on Programming Languages and Systems, 9, 3, 319-349 (1987) · Zbl 0623.68012
[9] Gallagher, K. B.; Lyle, J. R., Using program slicing in software maintenance, IEEE Transactions on Software Engineering, 17, 8, 751-761 (1991)
[10] Harman, M.; Binkley, D. W.; Danicic, S., Amorphous program slicing, Journal of Systems and Software, 68, 1, 45-64 (2003)
[11] Harman, M.; Hu, L.; Hierons, R. M.; Wegener, J.; Sthamer, H.; Baresel, A.; Roper, M., Testability transformation, IEEE Transactions on Software Engineering, 30, 1, 3-16 (2004)
[12] Horwitz, S.; Reps, T.; Binkley, D. W., Interprocedural slicing using dependence graphs, ACM Transactions on Programming Languages and Systems, 12, 1, 26-60 (1990)
[14] Komondoor, R.; Horwitz, S., Semantics-preserving procedure extraction, (Proceedings of the 27th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL-00) (Jan. 19-21, 2000), ACM Press: ACM Press N.Y.), 155-169 · Zbl 1323.68360
[16] Ottenstein, K. J.; Ottenstein, L. M., The program dependence graph in software development environments, Proceedings of the ACM SIGSOFT/SIGPLAN Software Engineering Symposium on Practical Software Development Environment. Proceedings of the ACM SIGSOFT/SIGPLAN Software Engineering Symposium on Practical Software Development Environment, SIGPLAN Notices, 19, 5, 177-184 (1984)
[18] Podgurski, A.; Clarke, L., A formal model of program dependences and its implications for software testing, debugging, and maintenance, IEEE Transactions on Software Engineering, 16, 9, 965-979 (1990)
[19] Ranganath, V. P.; Amtoft, T.; Banerjee, A.; Hatcliff, J.; Dwyer, M. B., A new foundation for control dependence and slicing for modern program structures, ACM Transactions on Programming Languages and Systems, 29, 5 (2007)
[20] Ren, X.; Ryder, B. G.; Störzer, M.; Tip, F., Chianti: a change impact analysis tool for Java programs, (Roman, G.-C.; Griswold, W. G.; Nuseibeh, B., 27th International Conference on Software Engineering (ICSE 2005) (15-21 May 2005), ACM: ACM St. Louis, Missouri, USA), 664-665
[22] Weiser, M., Program slicing, IEEE Transactions on Software Engineering, 10, 4, 352-357 (1984) · Zbl 0552.68004
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.