Please use this identifier to cite or link to this item:
Full metadata record
DC FieldValueLanguage
dc.contributor.authorDanicic, S-
dc.contributor.authorHierons, RM-
dc.contributor.authorLaurence, MR-
dc.identifier.citationMathematical Structures in Computer Science, 21: 1339-1362, Dec 2011en_US
dc.descriptionThis is the preprint version of the Article - Copyright @ 2011 Cambridge University Pressen_US
dc.description.abstractGiven a program, a quotient can be obtained from it by deleting zero or more statements. The field of program slicing is concerned with computing a quotient of a program that preserves part of the behaviour of the original program. All program slicing algorithms take account of the structural properties of a program, such as control dependence and data dependence, rather than the semantics of its functions and predicates, and thus work, in effect, with program schemas. The dynamic slicing criterion of Korel and Laski requires only that program behaviour is preserved in cases where the original program follows a particular path, and that the slice/quotient follows this path. In this paper we formalise Korel and Laski's definition of a dynamic slice as applied to linear schemas, and also formulate a less restrictive definition in which the path through the original program need not be preserved by the slice. The less restrictive definition has the benefit of leading to smaller slices. For both definitions, we compute complexity bounds for the problems of establishing whether a given slice of a linear schema is a dynamic slice and whether a linear schema has a non-trivial dynamic slice, and prove that the latter problem is NP-hard in both cases. We also give an example to prove that minimal dynamic slices (whether or not they preserve the original path) need not be unique.en_US
dc.description.sponsorshipThis work was partly supported by the Engineering and Physical Sciences Research Council, UK, under grant EP/E002919/1.en_US
dc.publisherCambridge University Pressen_US
dc.subjectProgram schemasen_US
dc.subjectProgram slicingen_US
dc.subjectHerbrand domainen_US
dc.subjectLinear schemasen_US
dc.titleOn the computational complexity of dynamic slicing problems for program schemasen_US
pubs.organisational-data/Brunel/Brunel (Active)-
pubs.organisational-data/Brunel/Brunel (Active)/School of Info. Systems, Comp & Maths-
pubs.organisational-data/Brunel/Research Centres (RG)-
pubs.organisational-data/Brunel/Research Centres (RG)/CIKM-
pubs.organisational-data/Brunel/School of Information Systems, Computing and Mathematics (RG)-
pubs.organisational-data/Brunel/School of Information Systems, Computing and Mathematics (RG)/CIKM-
Appears in Collections:Publications
Computer Science
Dept of Computer Science Research Papers

Files in This Item:
File Description SizeFormat 
dyn.intro.pdf215.88 kBAdobe PDFView/Open

Items in BURA are protected by copyright, with all rights reserved, unless otherwise indicated.