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]

Preview

Text 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:	Article
Identification Number (DOI):	https://doi.org/10.1016/j.jlap.2007.02.008
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: http://www.elsevier.com/about/open-access/open-access-policies/oa-license-policy/elsevier-user-license
Keywords:	Program schemas; Program slicing; Decidability; Conservative schemas; Liberal schemas; Free schemas; Linear schemas
Departments, Centres and Research Units:	Computing
Dates:	Date Event July 2007 Published
Item ID:	10583
Date Deposited:	27 Aug 2014 10:54
Last Modified:	29 Apr 2020 16:00
Peer Reviewed:	Yes, this version has been peer-reviewed.
URI:	https://research.gold.ac.uk/id/eprint/10583

View statistics for this item...

Edit Record (login required)