author: Ronald Burgman
title: Partial-order reduction in a dynamic context
committee: Arend Rensink ,
Alfons Laarman ,
Stefano Schivo
end: October 2012


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 that is able to handle Petri nets and to determine how the algorithm functions in practical situations.

Additional Resources

  1. The paper