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 Link


[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
[2] ARTEMIS consortium, The embedded computing systems initiative (ARTEMIS), 2007.
[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)
[13] M. Kamkar, Interprocedural dynamic slicing with applications to debugging and testing. PhD Thesis, Department of Computer Science and Information Science, Linköping University, Sweden, 1993. Available as Linköping Studies in Science and Technology, Dissertations, Number 297.
[14] Komondoor, R.; Horwitz, S., Semantics-preserving procedure extraction, (), 155-169 · Zbl 1323.68360
[15] A. Lakhotia, P. Singh, Challenges in getting formal with viruses, Virus Bulletin, Sept. 2003.
[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, SIGPLAN notices, 19, 5, 177-184, (1984)
[17] A. Podgurski, The significance of program dependences for software testing, de-bugging, and maintenance, PhD thesis, Computer and Information Science Department, University of Massachusetts, Amherst, 1989.
[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, (), 664-665
[21] M. Weiser, Program slices: Formal, psychological, and practical investigations of an automatic program abstraction method, PhD thesis, University of Michigan, Ann Arbor, MI, 1979.
[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.