TY - JOUR
T1 - Equivalence of linear, free, liberal, structured program schemas is decidable in polynomial time
AU - Danicic, S
AU - Harman, M
AU - Hierons, R
AU - Howroyd, J
AU - Laurence, M R
PY - 2007/3/22
Y1 - 2007/3/22
N2 - A program schema defines a class of programs, all of which have identical statement structure, but whose expressions may differ. We define a class of syntactic similarin, binary relations between linear structured schemas, which characterise schema equivalence for structured schemas that are linear, free and liberal. In this paper we report that similarity implies equivalence for linear schemas, and that a near-converse holds for schemas that are linear, free and liberal. We also show that the similarity of two linear schemas is polynomial-time decidable. Our main result considerably extends the class of program schemas for which equivalence is known to be decidable, and suggests that linearity is a constraint worthy of further investigation. (c) 2006 Elsevier B.V All rights reserved
AB - A program schema defines a class of programs, all of which have identical statement structure, but whose expressions may differ. We define a class of syntactic similarin, binary relations between linear structured schemas, which characterise schema equivalence for structured schemas that are linear, free and liberal. In this paper we report that similarity implies equivalence for linear schemas, and that a near-converse holds for schemas that are linear, free and liberal. We also show that the similarity of two linear schemas is polynomial-time decidable. Our main result considerably extends the class of program schemas for which equivalence is known to be decidable, and suggests that linearity is a constraint worthy of further investigation. (c) 2006 Elsevier B.V All rights reserved
U2 - 10.1016/j.tcs.2006.10.001
DO - 10.1016/j.tcs.2006.10.001
M3 - Article
VL - 373
SP - 1
EP - 18
JO - Theoretical Computer Science
JF - Theoretical Computer Science
IS - 1-2
ER -