Equivalence of linear, free, liberal, structured program schemas is decidable in polynomial time

Greibach, 1975, vol. 36 Manna, 1974 A.K. Chandra, On the decision problems of program schemas with commutative and invertable functions, in: Conference Record of the ACM Symposium on Principles of Programming Languages, ACM SIGACT-SIGPLAN, Boston, Massachusetts, 1973, pp. 235–242 A.K. Chandra, Z. Manna, Program schemas with equality, in: Conference Record, Fourth Annual ACM Symposium on Theory of Computing, Denver, Colorado, 1972, pp. 52–64 Chandra, 1975, On the power of programming features, Computer Languages, 1, 219, 10.1016/0096-0551(75)90032-6 Laurence, 2002, Equivalence of conservative, free, linear schemas is decidable, Theoretical Computer Science, 290, 831, 10.1016/S0304-3975(02)00374-2 M.R. Laurence, S. Danicic, M. Harman, R. Hierons, J. Howroyd, Equivalence of linear, free, liberal, structured program schemas is decidable in polynomial time, Tech. Rep. ULCS-04-014, University of Liverpool, 2004. Electronically available at http://www.csc.liv.ac.uk/research/techreports/ M.S. Paterson, Equivalence problems in a model of computation, Ph.D. Thesis, University of Cambridge, UK, 1967 Ashcroft, 1975, Translating program schemas to while-schemas, SIAM Journal on Computing, 4, 125, 10.1137/0204011 Ianov, 1960, vol. 1, 82 Sabelfeld, 1990, An algorithm for deciding functional equivalence in a new class of program schemes, Journal of Theoretical Computer Science, 71, 265, 10.1016/0304-3975(90)90201-R De Lucia, 1996, Understanding function behaviours through program slicing, 9 Canfora, 1994, Software salvaging based on conditions, 424 Cimitile, 1996, A specification driven slicing process for identifying reusable functions, Software Maintenance: Research and Practice, 8, 145, 10.1002/(SICI)1096-908X(199605)8:3<145::AID-SMR127>3.0.CO;2-9 Gallagher, 1991, Using program slicing in software maintenance, IEEE Transactions on Software Engineering, 17, 751, 10.1109/32.83912 Gallagher, 1992, Evaluating the surgeon’s assistant: Results of a pilot study, 236 Weiser, 1985, Experiments on slicing–based debugging aids, 187 Agrawal, 1993, Debugging with dynamic slicing and backtracking, Software — Practice and Experience, 23, 589, 10.1002/spe.4380230603 M. Kamkar, Interprocedural dynamic slicing with applications to debugging and testing, Ph.D. Thesis, Department of Computer Science and Information Science, Linköping University, Sweden, available as Linköping Studies in Science and Technology, Dissertations, Number 297, 1993 J.R. Lyle, M. Weiser, Automatic program bug location by program slicing, in: 2nd International Conference on Computers and Applications, IEEE Computer Society Press, Los Alamitos, CA, USA, Peking, 1987, pp. 877–882 Binkley, 1998, vol.~40, 583 Gupta, 1992, An approach to regression testing using slicing, 299 M. Harman, S. Danicic, Using program slicing to simplify testing, in: 2nd EuroSTAR Conference on Software Testing Analysis and Review, Brussels, 1994 Canfora, 1994, RE2: Reverse engineering and reuse re-engineering, Journal of Software Maintenance: Research and Practice, 6, 53, 10.1002/smr.4360060202 Simpson, 1993, Recoup—Maintaining Fortran, ACM Fortran Forum, 12, 26, 10.1145/174245.174252 Beck, 1993, Program and interface slicing for reverse engineering, 509 Cimitile, 1995, Identifying reusable functions using specification driven program slicing: a case study, 124 Horwitz, 1989, Integrating non-interfering versions of programs, ACM Transactions on Programming Languages and Systems, 11, 345, 10.1145/65979.65980 Bieman, 1994, Measuring functional cohesion, IEEE Transactions on Software Engineering, 20, 644, 10.1109/32.310673 J.J. Thuss, An investigation into slice-based cohesion metrics, Master’s Thesis, Michigan Technological University, 1988 A. Lakhotia, Rule-based approach to computing module cohesion, in: Proceedings of the 15th Conference on Software Engineering, ICSE-15, 1993, pp. 34–44 Binkley, 1996, vol. 43, 1 De Lucia, 2001, Program slicing: methods and applications, 142 F. Tip, A survey of program slicing techniques, Tech. Rep. CS-R9438, Centrum voor Wiskunde en Informatica, Amsterdam, 1994 M. Weiser, Program slices: Formal, psychological, and practical investigations of an automatic program abstraction method, Ph.D. Thesis, University of Michigan, Ann Arbor, MI, 1979 Danicic, 2006, Static program slicing algorithms are minimal for free liberal program schemas, The Computer Journal, 48, 737, 10.1093/comjnl/bxh121 M.R. Laurence, Characterising minimal semantics-preserving slices of function-linear, free, liberal program schemas, in: Theory and Foundations of Programming Language Interference and Dependence, Journal of Logic and Algebraic Programming (2006) (special issue) (submitted for publication)