Discovering block-structured process models from incomplete event logs

One of the main challenges in process mining is to discover a process model describing observed behaviour in the best possible manner. Since event logs only contain example behaviour and one cannot assume to have seen all possible process executions, process discovery techniques need to be able to handle incompleteness. In this paper, we study the effects of such incomplete logs on process discovery. We analyse the impact of incompleteness of logs on behavioural relations, which are an abstraction often used by process discovery techniques. We introduce probabilistic behavioural relations that are less sensitive to incompleteness, and exploit these relations to provide a more robust process discovery algorithm. We prove this algorithm to be able to rediscover a model of the original system. Furthermore, we show in experiments that our approach even rediscovers models from incomplete event logs that are much smaller than required by other process discovery algorithms. Keywords: process discovery, block-structured process models, rediscoverability, process trees