Learning Workflow Petri Nets

• Autorzy: Esparza, J. , Leucker, M. , Schlund, M.
• Języki publikacji: EN

Abstrakty

EN

Workflow mining is the task of automatically producing a workflow model from a set of event logs recording sequences of workflow events; each sequence corresponds to a use case or workflow instance. Formal approaches to workflow mining assume that the event log is complete (contains enough information to infer the workflow) which is often not the case. We present a learning approach that relaxes this assumption: if the event log is incomplete, our learning algorithm automatically derives queries about the executability of some event sequences. If a teacher answers these queries, the algorithm is guaranteed to terminate with a correct model. We provide matching upper and lower bounds on the number of queries required by the algorithm, and report on the application of an implementation to some examples.

Słowa kluczowe

EN

workflow nets; Petri net; learning algorithm

• Czasopismo: Fundamenta Informaticae
• Rocznik: 2011
• Tom: Vol. 113, nr 3/4
• Strony: 205-228
• Opis fizyczny: Bibliogr. 20 poz., tab., wykr.

Twórcy

autor

Esparza, J.

autor

Leucker, M.

autor

Schlund, M.

• Technische Universität München Boltzmannstr. 3, 85748 Garching, Germany,

Bibliografia

• [1] van der Aalst, W., van Hee, K.: Workflow Management. Models, Methods, and Systems., MIT Press, 2004.
• [2] van der Aalst, W. M. P.: The Application of Petri Nets to Workflow Management, Journal of Circuits, Systems, and Computers, 8(1), 1998, 21-66.
• [3] van der Aalst, W. M. P., van Dongen, B. F., Günther, C. W., Mans, R. S., de Medeiros, A. K. A., Rozinat, A., Rubin, V., Song, M., Verbeek, H. M. W. E., Weijters, A. J. M. M.: ProM 4.0: Comprehensive Support for eal Process Analysis, ICATPN, 2007.
• [4] van der Aalst, W. M. P., van Dongen, B. F., Herbst, J., Maruster, L., Schimm, G., Weijters, A. J. M. M.: Workflow mining: A survey of issues and approaches, Data Knowl. Eng., 47(2), 2003, 237-267.
• [5] Agrawal, R., Gunopulos, D., Leymann, F.: Mining Process Models from Workflow Logs, EDBT, 1998.
• [6] Andersen, H. R.: An Introduction to Binary Decision Diagrams, Technical report, 1999.
• [7] Angluin, D.: Learning Regular Sets from Queries and Counterexamples, Information and Computation, 75(2), 1987, 87-106, ISSN 0890-5401.
• [8] Badouel, E., Bernardinello, L., Darondeau, P.: Polynomial Algorithms for the Synthesis of Bounded Nets, TAPSOFT '95: Proceedings of the 6th International Joint Conference CAAP/FASE on Theory and Practice of Software Development, Springer-Verlag, London, UK, 1995, ISBN 3-540-59293-8.
• [9] Badouel, E., Darondeau, P.: On the synthesis of general Petri nets, Technical report, INRIA, 1996.
• [10] Bergenthum, R., Desel, J., Kölbl, C., Mauser, S.: Experimental results on process mining based on regions of languages, CHINA 2008, workshop at the Applications and theory of Petri nets : 29th international conference, 2008.
• [11] Bergenthum, R., Desel, J., Lorenz, R., Mauser, S.: Process Mining Based on Regions of Languages, BPM, 2007.
• [12] Bergenthum, R., Desel, J., Mauser, S., Lorenz, R.: Construction of Process Models from Example Runs, T. Petri Nets and Other Models of Concurrency, 2, 2009, 243-259.
• [13] Bollig, B., Katoen, J.-P., Kern, C., Leucker, M.: Learning Communicating Automata from MSCs, IEEE Transactions on Software Engineering (TSE), 36(3), May/June 2010, 390-408.
• [14] Bollig, B., Katoen, J.-P., Kern, C., Leucker, M., Neider, D., Piegdon, D.: libalf: the Automata Learning Framework, Proceedings of the 22nd International Conference on Computer-Aided Verification (CAV'10), 6174, Springer, 2010.
• [15] Chow, T. S.: Testing Software Design Modeled by Finite-State Machines, TSE, 4(3), May 1978, 178-187, Special collection based on COMPSAC.
• [16] Kindler, E., Rubin, V., Schäfer, W.: Process Mining and Petri Net Synthesis, Business Process Management Workshops, 2006.
• [17] Rubin, V., Günther, C. W., van der Aalst, W. M. P., Kindler, E., van Dongen, B. F., Schäfer, W.: Process Mining Framework for Software Processes, ICSP, 2007.
• [18] SAP AG: SAP Business Workflow Demo Examples (BC-BMT-WFM), 2001.
• [19] Vasilevski, M. P.: Failure Diagnosis of Automata, Cybernetic, 9(4), 1973, 653-665.
• [20] Verbeek, H. M.: Verification of WF-nets, Ph.D. Thesis, Technische Universiteit Eindhoven, 2004