Efficient comparison of program slices

DOI10.1007/BF01261653MaRDI QIDQ758192zbMATH OpenFDO

Authors Susan Horwitz, Thomas Reps

Publication date 1991

Published in Acta Informatica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF01261653

zbMATH Keywords

intermediate program representationprogram dependence graphprogram slices

Mathematics Subject Classification ID

General topics in the theory of software (68N01) Theory of compilers and interpreters (68N20) Graph theory (including graph drawing) in computer science (68R10)

Review text

The slice of a program with respect to a component c is a projection of the program that includes all components that might affect (either directly or transitively) the values of the variables used at c. Slices can be extracted particularly easily from a program representation called a program dependence graph, originally introduced as an intermediate program representation for performing optimizing, vectorizing, and parallelizing transformations. This paper presents a linear-time algorithm for determining whether two slices of a program dependence graph are isomorphic.

Recommendations

• An efficient method for computing dynamic program slices
• A parallel algorithm for static program slicing
• On optimal slicing of parallel programs
• scientific article; zbMATH DE number 2087514
• Program Slicing
• A novel formal approach to program slicing

Cites work

• Group-theoretic algorithms and graph isomorphism
• scientific article; zbMATH DE number 3876561 (Why is no real title available?)
• scientific article; zbMATH DE number 177792 (Why is no real title available?)
• Isomorphism of graphs of bounded valence can be tested in polynomial time
• On the Number of Operations Simultaneously Executable in Fortran-Like Programs and Their Resulting Speedup
• Program Slicing
• The program dependence graph and its use in optimization

Cited in

(7)

• An efficient method for computing dynamic program slices
• Abstract similarity analysis
• Integrating different versions of programs with backward and forward slices
• On the computational complexity of dynamic slicing problems for program schemas
• scientific article; zbMATH DE number 2087514 (Why is no real title available?)
• scientific article; zbMATH DE number 1832217 (Why is no real title available?)
• An optimal algorithm for the construction of the system dependence graph

This page was built for publication: Efficient comparison of program slices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q758192)