Brunel University Research Archive (BURA) >
Research Areas >
Computer Science >

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
Publication 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
Software Engineering (B-SERC)
Dept of Computer Science Research Papers

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.