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 |
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. |
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: | Computer Science Dept of Computer Science Research Papers Software Engineering (B-SERC) |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
TCSB.1114.pdf | 315.11 kB | Adobe PDF | View/Open |
Items in BURA are protected by copyright, with all rights reserved, unless otherwise indicated.