Scalable conformance checking of business processes

Given a process model representing the expected behavior of a business process, and given an event log recording its actual execution, the problem of business process conformance checking is that of detecting and describing the differences between the process model and the event log. A desirable feature is to produce a minimal yet complete set of behavioral differences. Existing conformance checking techniques that achieve these properties do not scale up to real-life process models and event logs. This paper presents a technique that addresses this shortcoming by exploiting scalable automata-based techniques. A log is converted into a deterministic automaton in a lossless manner, the input process model is converted into another minimal automaton, and a minimal error- correcting synchronized product of the two automata is calculated using an admissible A* heuristic. The resulting automaton is used to extract alignments between traces produced by the model and traces in the log, or statements describing behavior observed in the log but not captured in the model. An evaluation based on real-life models and logs shows that the proposed technique significantly outperforms a state of the art technique for complete conformance checking