Process Discovery from Dependence-Complete Event Logs

Process mining, especially process discovery, has been utilized to extract process models from event logs. One challenge faced by process discovery is to identify concurrency effectively. State-of-the-art approaches employ activity orders in traces to undertake process discovery and they require stringent completeness notions of event logs. Thus, they may fail to extract appropriate processes when event logs cannot meet the completeness criteria. To address this problem, we propose in this paper a novel technique which leverages activity dependences in traces. Based on the observation that activities with no dependencies can be executed in parallel, our technique is in a position to discover processes with concurrencies even if the logs fail to meet the completeness criteria. That is, our technique calls for a weaker notion of completeness. We evaluate our technique through experiments on both real-world and synthetic event logs, and the conformance checking results demonstrate the effectiveness of our technique and its relative advantages compared with state-of-the-art approaches.