Incremental Process Discovery using Petri Net Synthesis

• Autorzy: Badouel E. , Schlachter U.

Identyfikatory

DOI

10.3233/FI-2017-1548

• Języki publikacji: EN

Abstrakty

EN

Process discovery aims at constructing a model from a set of observations given by execution traces (a log). Petri nets are a preferred target model in that they produce a compact description of the system by exhibiting its concurrency. This article presents a process discovery algorithm using Petri net synthesis, based on the notion of region introduced by A. Ehrenfeucht and G. Rozenberg and using techniques from linear algebra. The algorithm proceeds in three successive phases which make it possible to find a compromise between the ability to infer behaviours of the system from the set of observations while ensuring a parsimonious model, in terms of fitness, precision and simplicity. All used algorithms are incremental which means that one can modify the produced model when new observations are reported without reconstructing the model from scratch.

Słowa kluczowe

EN

region theory; Petri net synthesis; process discovery

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2017
• Tom: Vol. 154, nr 1/4
• Strony: 1--13
• Opis fizyczny: Bibliogr. 14 poz.., rys.

Twórcy

autor

Badouel E.

• Inria Rennes-Bretagne Atlantique, Campus de Beaulieu, F35042 Rennes, France

autor

Schlachter U.

• Department of Computing Science, Carl von Ossietzky Universität Oldenburg, D-26111 Oldenburg, Germany

Bibliografia

• [1] Ehrenfeucht A, Rozenberg G. Partial 2-structures; Part I: Basic Notions and the Representation Problem. Acta Informatica, 1990;27:315–342. doi:10.1007/BF00264611.
• [2] Ehrenfeucht A, Rozenberg G. Partial 2-structures; Part II: State Spaces of Concurrent Systems. Acta Informatica, 1990;27:343–368. doi:10.1007/BF00264612.
• [3] Badouel E, Bernardinello L, Darondeau P. Petri Net Synthesis. Springer, 2015. doi:10.1007/978-3-662-47967-4.
• [4] Badouel E, Bernardinello L, Darondeau P. Polynomial Algorithms for the Synthesis of Bounded Nets. In: Mosses PD, Nielsen M, Schwartzbach MI (eds.), TAPSOFT’95, volume 915 of Lecture Notes in Computer Science. Springer, 1995 pp. 364–378. doi:10.1007/3-540-59293-8 207.
• [5] Darondeau P. Deriving Unbounded Petri Nets from Formal Languages. In: CONCUR’98 Concurrency Theory, volume 1466 of Lecture Notes in Computer Science. Springer, 1998 pp. 533–548. doi:10.1007/BFb0055646.
• [6] Lorenz R, Juhás G, Mauser S. How to synthesize nets from languages - A Survey. In: Proceedings of the 2007 Winter Simulation Conference. IEEE, 2007 pp. 637–647. doi:10.1109/WSC.2007.4419657.
• [7] Carmona J, Cortadella J, Kishinevsky M. A region-based algorithm for discovering Petri nets from event logs. In: M Dumas MS M Reichest (ed.), BPM 2008, volume 5240 of Lecture Notes in Computer Science. Springer, 2008 pp. 358–373. doi:10.1007/978-3-540-85758-7 26.
• [8] Best E, Devillers R. Synthesis and reengineering of persistent systems. Acta Informatica, 2015;52(1):35–60. doi:10.1007/s00236-014-0209-7.
• [9] Best E, Devillers R. Characterisation of the state spaces of marked graph Petri nets. Information and Computation, 2017;253:399–410. doi:10.1016/j.ic.2016.06.006.
• [10] van der Werf JMEM, van Dongen BF, Hurkens CAJ, Serebrenik A. Process discovery using integer linear programming. Fundamenta Informaticae, 2009;94(3-4):387–412. URL http://dl.acm.org/citation.cfm?id=1662594.1662600.
• [11] van Zelst SJ, van Dongen BF, van der Aalst WMP. ILP-Based Process Discovery Using Hybrid Regions. In: Proceedings of ATAED 2015. 2015 pp. 47–61. URL http://ceur-ws.org/Vol-1371/paper04.pdf.
• [12] van der Aalst WMP. Process Mining-Discovery, Conformance and Enhancement of Business Processes. Springer, 2001. doi:10.1007/978-3-642-19345-3.
• [13] van der Aalst WMP. Process Mining - Data Science in Action. Springer, 2016. doi:10.1007/978-3-662-49851-4.
• [14] Alchourrón CE, Gärdenfors P, Makinson D. On the Logic of Theory Change: Partial Meet Contraction and Revision Functions. J. Symb. Log., 1985;50(2):510–530. doi:10.2307/2274239.