Tech Reports

ULCS-04-014

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

Abstract

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.

For each technical report listed here, copyright and all intellectual property rights remain with the respective authors. Copyright is effective from the year of publication in each case. By downloading a file from this page, you agree to use it only for purposes of research and scholarship. Any other use of this material or storage of it in any medium or its sale or distribution in any form is expressly forbidden without prior written permission from the authors concerned.