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

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

260 Citations (Scopus)
1 Downloads (Pure)

Abstract

Process discovery is the problem of, given a log of observed behaviour, finding 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 fitting model (i.e., able to reproduce all observed behaviour) that is sound (free of deadlocks and other anomalies) in finite time. We present an extensible framework to discover from any given log a set of block-structured process models that are sound and fit 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, fitting, block-structured model from any given log; we give sufficient conditions on the log for which our algorithm returns a model that is language-equivalent to the process model underlying the log, including unseen behaviour. The technique is implemented in a prototypical tool.
Original languageEnglish
Title of host publicationApplication and Theory of Petri Nets and Concurrency (34th International Conference, PETRI NETS 2013, Milan, Italy, June 24-28, 2013. Proceedings)
EditorsJ.M. Colom, J. Desel
Place of PublicationBerlin
PublisherSpringer
Pages311-329
ISBN (Print)978-3-642-38696-1
DOIs
Publication statusPublished - 2013
Event34th International Conference on Application and Theory of Petri Nets and Concurrency (Petri Nets 2013), June 24-28, 2013, Milan, Italy - Milan, Italy
Duration: 24 Jun 201328 Jun 2013
http://www.mc3.disco.unimib.it/petrinets2013/

Publication series

NameLecture Notes in Computer Science
Volume7927
ISSN (Print)0302-9743

Conference

Conference34th International Conference on Application and Theory of Petri Nets and Concurrency (Petri Nets 2013), June 24-28, 2013, Milan, Italy
Abbreviated titlePetri Nets 2013
CountryItaly
CityMilan
Period24/06/1328/06/13
Internet address

Fingerprint

Dive into the research topics of 'Discovering block-structured process models from event logs : a constructive approach'. Together they form a unique fingerprint.

Cite this