Discovering block-structured process models from event logs : a constructive approach

Process discovery is the problem of, given a log of observed behaviour, ¿nding a process model that ‘best’ describes this behaviour. A large variety of process discovery algorithms has been proposed. However, no existing algorithm guarantees to return a ¿tting model (i.e., able to reproduce all observed behaviour) that is sound (free of deadlocks and other anomalies) in ¿nite time. We present an extensible framework to discover from any given log a set of block-structured process models that are sound and ¿t the observed behaviour. In addition we characterise the minimal information required in the log to rediscover a particular process model. We then provide a polynomial-time algorithm for discovering a sound, ¿tting, block-structured model from any given log; we give suf¿cient conditions on the log for which our algorithm returns a model that is languageequivalent to the process model underlying the log, including unseen behaviour. The technique is implemented in a prototypical tool.