Tech Reports


Equivalence of Linear, Free, Liberal, Structured Program Schemas is Decidable in Polynomial Time

Michael R. Laurence, Sebastian Danicic, Mark Harman, Rob Hierons and John Howroyd


A program schema defines a class of programs, all of which have identical statement structure, but whose expressions may differ. We prove that given any two structured schemas which are linear, free and liberal, it is decidable whether they are equivalent. This 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.

[Full Paper]