Brunel University Research Archive (BURA) >
Research Areas >
Information Systems and Computing >

Please use this identifier to cite or link to this item: http://bura.brunel.ac.uk/handle/2438/697

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.
URI: http://www.elsevier.com/wps/find/journaldescription.cws_home/505625/description#description
http://bura.brunel.ac.uk/handle/2438/697
ISSN: 03043975
Appears in Collections:B-SERC Research Papers
Information Systems and Computing
School of Information Systems, Computing and Mathematics 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.

 


Library (c) Brunel University.    Powered By: DSpace
Send us your
Feedback. Last Updated: September 14, 2010.
Managed by:
Hassan Bhuiyan