Please use this identifier to cite or link to this item:
|Title:||Equivalence of linear, free, liberal, structured program schemas is decidable in polynomial time|
|Citation:||Theoretical Computer Science, 373: 1-18|
|Abstract:||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 similarity binary relations between linear structured schemas and show that these relations characterise schema equivalence for structured schemas which are linear, free and liberal. In this paper we prove that similarity implies equivalence for linear schemas; the proof of a near-converse for schemas that are linear, free and liberal (LFL), which is much longer, is given in a Technical Report, which also contains the results of this paper. 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.|
|Appears in Collections:||Computer Science|
Dept of Computer Science Research Papers
Software Engineering (B-SERC)
Items in BURA are protected by copyright, with all rights reserved, unless otherwise indicated.