Open AccessProperties of Unfolding-based Meta-level Systems
Author(s) -
Torben Amtoft Hansen
Publication year - 1991
Publication title -
daimi pb
Language(s) - English
Resource type - Journals
eISSN - 2245-9316
pISSN - 0105-8517
DOI - 10.7146/dpb.v20i348.6578
Subject(s) - transformation (genetics) , computer science , sequence (biology) , set (abstract data type) , constant (computer programming) , program transformation , algorithm , theoretical computer science , order (exchange) , programming language , genetics , gene , biochemistry , chemistry , biology , finance , economics
It is well known that one can often transform a given program into a more efficient equivalent: by introducing some ''eureka definitions'' and then performing a sequence of unfold/fold/... steps, or by applying the technique of dynamic programming. A framework is set up, general enough to account for both of those techniques, enabling us to reason formally about complexity improvements. It is shown that under the absence of certain features, transformation is able to speed up execution time by at most a constant factor only. In order to have a chance of achieving a more substantial speed up, a transformation system thus must contain at least one of those features. Finally, it is shown that under very weak conditions termination properties are preserved by transformation.