Hide/Show Apps

Deriving a dynamic programming algorithm for batch scheduling in the refinement calculus

Download
2003
Aktuğ, İrem
Refinement Calculus is a formalization of stepwise program construction.In this approach a program is derived from its specification by applying refinement rules.The Refinement Calculator,developed at TUCS,Finland,provides tool support for the Refinement Calculus.This thesis presents a case study aiming to evaluate the applicability of the theory and the performance of the tool.The Refinement Calculator is used for deriving a dynamic progaramming algorithm for a single-machine batch scheduling problem.A quadratic algoritm is derived by refining a formal specification of this problem into executable code.The need for stronger support for relevant domain theories and abstraction mechanisms in the target language have been noted.