Process Discovery via Precedence Constraints

A key task in process mining consists of building a graph of causal dependencies over process activities, which can then be used to derive more expressive models in some high-level modeling language. An approach to accomplish this task is presented where the learning process can exploit the background knowledge that, in many cases, is available to the analysts taking care of the process (re-)design. The method is based on encoding the information gathered from the log and the (possibly) given background knowledge in terms of precedence constraints, i.e., constraints over the topology of the graphs. Learning algorithms are eventually formulated in terms of reasoning problems over precedence constraints, and the computational complexity of such problems is thoroughly analyzed by tracing their tractability frontier. The whole approach has been implemented in a prototype system leveraging a solid constraint programming platform, and results of experimental activity are reported. © 2012 The Author(s).