Master Thesis – Investigation and Discovery of Uniwired Petri Nets
More and more processes executed in companies are supported by information systems, which store each event executed in a so-called event log. In the context of process mining, many algorithms and software tools have been developed to utilize the data contained in such event logs: By analyzing the execution of a process, as captured in the log, we get insights on deviations of the ideal process model, bottlenecks and waste of resources.
The field of process discovery focusses on extracting a model from a given event log, that reflects the process underlying the log: The observed events are put into relation to each other, preconditions, choices, concurrency, etc. are discovered, and brought together in a process model, e.g. a Petri net. Process discovery is non-trivial for a variety of reasons. Ideally, a discovered model should be able to produce the behavior contained within the event log (fitness), not allow for behavior that was not observed (precision), represent all relevant dependencies between the events and at the same time be simple enough to be understood by a human interpreter. It is rarely possible to fulfill all these requirements simultaneously. Based on the capabilities and focus of the used algorithm, the discovered models can vary greatly.
Most existing algorithms that are able to discover precise models with complex control-flow structures, in particular long-term dependencies, do not only need excessive computation time but also return overly complex and hard-to-read models. One recently proposed solution is to focus on a new subclass of Petri nets, so-called uniwired Petri nets, which aim to combine simplicity with expressiveness. As a first algorithm to discover such uniwired Petri nets, a variant of eST-Miner was introduced.
In this thesis, the student investigates the expressiveness of uniwired Petri nets, discovering their capabilities and restrictions, and positions them in relation to other net classes. Additionally, an algorithm discovering such nets is developed, implemented, tested and evaluated. This could be a completely new algorithm or an extension of the proposed eST-Miner variant. Depending on the student’s interests and ideas, more focus may be given to one of these subtopics. The student presents the achievements in the context of their thesis paper as well as an intermediate and final presentation.
This thesis includes implementation as well as formal reasoning and proof of the theoretical foundations and guarantees. We expect knowledge of basic computer science concepts, good theoretical foundations, programming skills (Python and/or Java) and an interest in theoretical and practical aspects of process mining and Petri net theory.
Prof.dr.ir. Wil van der Aalst
Lisa Mannel (primary advisor) and Sebastiaan van Zelst (secondary advisor)
For more Information