Characterizing minimal semantics-preserving slices of function-linear, free, liberal program schemas

Laurence, Michael. 2007. Characterizing minimal semantics-preserving slices of function-linear, free, liberal program schemas. The Journal of Logic and Algebraic Programming, 72(2), pp. 157-172. ISSN 1567-8326 [Article]

COM-LaurenceM-2007.pdf - Published Version
Available under License Creative Commons Attribution Non-commercial Share Alike.

Download (305kB) | Preview

Abstract or Description

A program schema defines a class of programs, all of which have identical statement structure, but whose functions and predicates may differ. A schema thus defines an entire class of programs according to how its symbols are interpreted. As defined in this paper, a slice of a schema is obtained from a schema by deleting some of its statements. We prove that given a schema S which is function-linear, free and liberal, and a slicing criterion defined by the final value of a given variable after execution of any program defined by S, the minimal slice of S which respects this slicing criterion contains only the symbols ‘needed’ by the variable according to the data dependence and control dependence relations used in program slicing, which is the symbol set given by Weiser’s static slicing algorithm. Thus this algorithm gives minimal slices for programs representable by function-linear, free, liberal schemas. We also prove a similar result with termination behaviour used as a slicing criterion. This strengthens a recent result, in which S was required to be linear, free and liberal, and termination behaviour as a slicing criterion was not considered.

Item Type:


Identification Number (DOI):

Additional Information:

This work was supported by a grant from the Engineering and Physical Sciences Research Council, Grant EP/E002919/1.

This is an Elsevier Open Archive article. Articles published under an Elsevier user license are protected by copyright and may be used for non-commercial purposes. For further details:


Program schemas; Program slicing; Decidability; Conservative schemas; Liberal schemas; Free schemas; Linear schemas

Departments, Centres and Research Units:



July 2007Published

Item ID:


Date Deposited:

27 Aug 2014 10:54

Last Modified:

29 Apr 2020 16:00

Peer Reviewed:

Yes, this version has been peer-reviewed.


View statistics for this item...

Edit Record Edit Record (login required)