On the computational complexity of dynamic slicing problems for program schemas

DOI10.1017/S0960129511000223MaRDI QIDQ3103616zbMATH OpenOpenAlexFDO

Authors Sebastian Danicic, Michael R. Laurence, Robert M. Hierons

Publication date 8 December 2011

Published in Mathematical Structures in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1705.07686

zbMATH Keywords

program slicingprogram slicing algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30)

Abstract: Given 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 which 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.

Recommendations

• Characterizing minimal semantics-preserving slices of function-linear, free, liberal program schemas
• Characterizing minimal semantics-preserving slices of predicate-linear, free, liberal program schemas
• Dynamic program slicing
• Program Slicing
• Efficient comparison of program slices

Cites work

• An algorithm deciding functional equivalence in a new class of program schemes
• Characterizing minimal semantics-preserving slices of function-linear, free, liberal program schemas
• Computing polynomial program invariants
• Dynamic program slicing
• Equivalence of conservative, free, linear program schemas is decidable
• Equivalence of linear, free, liberal, structured program schemas is decidable in polynomial time
• On Ianov's Program Schemata
• On formalised computer programs
• On the Computational Complexity of Program Scheme Equivalence
• Precise interprocedural dependence analysis of parallel programs
• Program Slicing
• Theoretical foundations of dynamic program slicing
• Translating Program Schemas to While-Schemas

Cited in

(6)

• scientific article; zbMATH DE number 1870530 (Why is no real title available?)
• Statistics and recognition for software birthmark based on clustering analysis
• On optimal slicing of parallel programs
• Characterizing minimal semantics-preserving slices of function-linear, free, liberal program schemas
• An efficient method for computing dynamic program slices
• Characterizing minimal semantics-preserving slices of predicate-linear, free, liberal program schemas

This page was built for publication: On the computational complexity of dynamic slicing problems for program schemas

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