Program slicing is a program simplification technique in which we eliminate parts of the program that are not of interest. For example, we might produce a (backwards static) slice of a program p at a given node n and for the variables in a set V - we can eliminate any statement of p that cannot affect the values of variables in V at n. Program slicing has the potential to help wherever complexity could be a problem.

There are a number of variants on slicing. For example, we could ask for the parts of the program affected by the node of interest (forwards slicing) - something that can help in ripple analysis. We also might have additional information when we slice, such as the exact input in which we are interested (dynamic slicing) or a condition that we can place on the input (conditioned slicing). We can also allow more general transformations to be applied to the program, rather than just deleting statements (amorphous slicing).

Our interest in program slicing led us to investigate program schemas. A program schema is an abstraction produced by replacing each expression in a program by a name (function or predicate name) and a list of parameters. This abstracts away details regarding what the actual expressions do. The hope is that problems, such as equivalence, will become decidable for classes of schemas.

The abstraction applied when using schemas correspond to that used in many program analysis techniques (such as program slicing and variable dependence analysis). It is also consistent with dataflow testing techniques. Thus, if we can answer questions about schemas we may well be able to make advancements in these areas.

• S. Danicic, R. M. Hierons, and M. Laurence, On the computational complexity of dynamic slicing problems for program schemas, Mathematical Structures in Computer Science (to appear).
• R. W. Barraclough, D. Binkley, S., Danicic, M. Harman, R. M. Hierons, A. Kiss, M. Laurence, L. Ouarbya, A Trajectory-based Strict Semantics for Program Slicing, Theoretical Computer Science, 411 11-13, pp. 1372-1386, 2010.
• S. Danicic, M. Harman, R. M. Hierons, J. Howroyd, and M. R. Laurence: Equivalence of Linear, Free, Liberal, Structured Program Schemas is Decidable in Polynomial time, Theoretical Computer Science, 373, pp. 1-18, 2007.
• S. Danicic, C. J. Fox, M. Harman, R. M. Hierons, J. Howroyd, and M. R. Laurence: Static Program Slicing Algorithms are Minimal for Free Liberal Program Schemas, The Computer Journal, 48 6, pp. 737-748, 2005.
• S. Danicic, M. Daoudi, C. Fox, M. Harman, R. M. Hierons, J. Howroyd, L. Ourabya, and M. Ward, 2005, ConSUS: a light-weight program conditioner, Journal of Systems and Software, 77 3, pp. 241-262.
• N. E. Gold, M. Harman, D. Binkley, and R. M. Hierons, 2005, Unifying program slicing and concept assignment for source code extraction, Software Practice and Experience, 35 10, pp. 997-1006.
• S. Danicic, C. J. Fox, M. Harman, R. M. Hierons, J. Howroyd, and M. R. Laurence, 2005, Static Program Slicing Algorithms are Minimal for Free Liberal Program Schemas, The Computer Journal, 48 6, pp. 737-748.
• C. Fox, S. Danicic, M. Harman and R. M. Hierons, 2004, ConSIT: A fully automated conditioned program slicer, Software Practice and Experience, 34 1, pp. 15-46.
• L. Hu, M. Harman, R. M. Hierons, and D. W. Binkley, 2004, Loop Squashing Transformations for Amorphous Slicing, IEEE Working Conference on Reverse Engineering (WCRE'2004),.
• M. Harman, D. Binkley, R. Singh and R. M. Hierons, 2004, Amorphous Procedure Extraction, 4th Workshop on Source Code Analysis and Manipulation (SCAM 2004), September 14th-15th, 2004, Chicago, Illinois, USA.
• S. Danicic, M. Daoudi, C. Fox, M. Harman, R. M. Hierons, J. Howroyd, L. Ourabya, and M. Ward, 2005, Light-weight program conditioning, Journal of Systems and Software.
• K. Mahdavi, M. Harman and R.M. Hierons, 2003, A Multiple Hill Climbing Approach to Software Module Clustering, 19th IEEE International Conference on Software Maintenance (ICSM 2003), Amsterdam, The Netherlands, 22-26 September 2003.
• A. De Lucia, M. Harman, R. Hierons, and J. Krinke, 2003, Unions of slices are not slices, IEEE Conference on Software Maintenance and Reengineering (CSMR 2003), Benevento, Italy, March 26-28, 2003.
• M. Laurence, S. Danicic, M. Harman, R. M. Hierons, and J. D. Howroyd: Equivalence of Conservative, Free, Linear Schemas is Decidable, Theoretical Computer Science, 290 1, pp. 831-862, 2002.
• R. M. Hierons, M. Harman, C. J. Fox, M. Daoudi, and L. Ouarbya, 2002, Conditioned slicing supports partition testing, The Journal of Software Testing, Verification and Reliability , 12 1, pp. 23-28.
• M. Harman, N. Gold, R. M. Hierons, 2002, Code Extraction Algorithms which Unify Slicing and Concept Assignment, Working Conference on Reverse Engineering (WCRE 2002), October 28 - November 1, Richmond, Virginia, USA.
• M. Harman and R. M. Hierons, 2001, An overview of Program Slicing, Software Focus, 2 3, pp. 85-92.
• M. Harman, R. M. Hierons, S. Danicic, M. Laurence, J. Howroyd and C. Fox, 2001, Node Coarsening Calculi for Program Slicing, IEEE Working Conference on Reverse Engineering (WCRE'2001), 2-5 October 2001 at Stuttgart, Germany.
• M. Harman, R. M. Hierons, C. Fox, S. Danicic, and J. Howroyd, 2001, Pre/Post Conditioned Slicing, IEEE International Conference on Software Maintenance (ICSM'2001), Florence, Italy, November 6th-10th.
• S. Danicic, C. Fox, M. Harman and R. Hierons, 2001 Backward Conditioning: a new program specialisation technique and its application to program comprehension, IEEE International Workshop on Program Comprehension (IWPC 2001). Toronto, Canada, May 12th-13th, 2001.
• S. Danicic, C. Fox, M. Harman and R. Hierons, 2000 ConSIT: A Conditioned Program Slicer IEEE International Conference on Software Maintenance (ICSM'2000). 4an Jose, California, USA, October 11-14, 2000.
• M. Harman, C. Fox, R. Hierons, D. Binkley, and S. Danicic, 1999, Program Simplification as a Means of Approximating Undecidable Propositions, 7th IEEE International Workshop on Program Comprehension (IWPC'99) , Carnegie Mellon University, Pittsburgh, PA, USA, May 5th - 7th, pages 208-217.

Back to Rob Hierons' home page

Last updated: May 2010.