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
Authors: Danicic, S
Harman, M
Hierons, RM
Howroyd, J
Laurence, MR
Issue Date: 2007
Publisher: Elsevier
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.
ISSN: 03043975
Appears in Collections:Computer Science
Dept of Computer Science Research Papers
Software Engineering (B-SERC)

Files in This Item:
File Description SizeFormat 
TCSB.1114.pdf315.11 kBAdobe PDFView/Open

Items in BURA are protected by copyright, with all rights reserved, unless otherwise indicated.