May 29, 2012: Ronald Burgman: Partial-order reduction in a dynamic context

May 29, 2012Partial-order reduction in a dynamic context
Room: Zi 5126Ronald Burgman

Partial-order reduction is a well known approach to reduce the state space explosion problem. The drawback of this approach is that it can only be applied in a static context, ie. a parallel system where the processes and the actions of these processes are known in advance.
In a dynamic context, like graph transformation systems, there is no clear definition of a process, and actions can dynamically be created and destroyed. Therefore static partial-order reduction cannot be applied. As a solution, a dynamic partial-order reduction algorithm was proposed by Kastenberg and Rensink, which is able to handle dynamic systems.
Although the theory behind the algorithm is clear, it has never actually been implemented. Therefore it is unknown if the theoretical advantages of the algorithm are actually preserved in practice. The goal of this master project is to create an implementation of the algorithm and to determine how the algorithm functions in practical situations.